Proth's theorem states that if p is a prime Proth number ( of the form k * 2^n + 1 with k odd and k < 2^n ), then for some integera, In mathematics, a Proth number, named after the amateur mathematician Francois Proth who first studied them, is a positive integer of the form where n is a nonnegative integer and k is odd and k> 2^n. ... The integers consist of the positive natural numbers (1, 2, 3, …), their negatives (−1, −2, −3, ...) and the number zero. ...
Where q = ( ( p-1)/2)
This means that if you can find some number a, that multiplied it by itself (p-1)/2 times and add 1, then if the result is divisible by p (see modular arithmetic), then the number is a prime. Modular arithmetic is a system of arithmetic for integers, where numbers wrap around after they reach a certain value — the modulus. ...
Numerical examples
Examples of the theorem include ( all p are Proth numbers):
for p = 3, 21 plus 1 = 3 is divisible by 3, so 3 is prime.
for p = 5, 32 plus 1 = 10 is divisible by 5, so 5 is prime.
for p = 13, 56 plus 1 = 15626 is divisible by 13, so 13 is prime.
for p = 9, there is no a such that a^4 + 1 is divisible by 9, so 9 is not prime.
History
Francois Proth found the theorem around 1878. 1878 was a common year starting on Tuesday (see link for calendar). ...
The new factor was found on a 350 MHz Pentium II computer, one of a number of machines in St. Patrick's College of Dublin City University running the program.
The program is named Proth.exe because one of the theorems of the self-taught farmer François Proth (1852-1879) is the heart of the program (see [7], [6, Theorem 102, page 79] or [8, page 52]):
Proth, Théorèmes sur les nombres premiers, Comptes Rendues Acad.
It is also a very useful test: it applies to Cullen primes, Fermat factors, the primes in the Sierpinski conjecture...
His "Proth.exe" program makes finding all these types of primes as easy as selecting the form you desire from a menu, choosing the starting values (here Ray Ballinger's Proth Range page's are especially helpful) and then letting the machine go.
Ray Ballinger's Proth Range Page's contains pages for coordinating the searches for Cullen primes, Woodall primes, "Proth" primes and the Sierpinski problem.
Feeds |
Contact