Proth Primes

Fermat a French lawyer and Mathematician stated that all numbers in the form of 2^{(2^p)} + 1 are prime. Numbers in this form
prime or not are called Fermat numbers .

Note that ^ means to the power of.

For p=0 we have Z = 2^{(2^0)} + 1 = 2+1 = 3 , so it is prime.
For p=1 we have Z = 2^{(2^1)} + 1 = 4+1 = 5 , so it is prime.
For p=2 we have Z = 2^{(2^2)} + 1 = 16+1 = 17 , so it is prime.
For p=3 we have Z = 2^{(2^3)} + 1 = 256+1 = 257 , so it is prime.
For p=4 we have Z = 2^{(2^4)} + 1 = 65536+1 = 65537 , so it is prime.
For p=5 we have Z = 2^{(2^5)} + 1 = 4294967296+1 = 4294967297 , which has a factor of 641 so it is not prime.

So lawyers don't know everything, but we all make mistakes sometimes. Lots more Fermat numbers like these have been
tested in the meantime and all of them proved to be non prime so far. Now it is a fact that if
a Fermat number F_m = 2^r + 1, where r = 2^m has a factor, this factor must be in the form of k.2ⁿ+1 . Using Proth's theorem
we can search for primes in this form and then test them against  Fermat numbers to see if it divides a Fermat number.
Proth was a farmer, don't know where he got the time for Mathematics.

Proth's theorem states that let N = k.2ⁿ+1 with 2ⁿ > k.   If there is an integer a such that
a^(N-1)/2 = -1 (mod N), then N is prime.

So currently there is a big search for such primes to test them against Fermat numbers as possible factors of Fermat numbers,
thereby proving that specific tested Fermat number as not prime. Currently 2006 there are only about 250 such prime divisors of Fermat numbers.
This means that we have only proven that about 250 Fermat numbers are not Prime.

Finding a Proth prime in itself is a great feat. I have found one so far, but it is not a factor of any Fermat number sadly.

Proth prime I discovered on 30/06/2006 is 49*(2^501238) + 1
This prime has 150 890 digits

We use mod theorem. If you don't know it, learn it. It is fun and very useful. For the lazy see my minute introduction to mod theorem.

Minute introduction to mod theorem

Mod theorem is all about integers, division and remainders .
Now 10 = 3 x 3 + 1 as remainder, or 10 divided by 3 is 3 and we have one as remainder.
We write this as 10 == 1 mod 3 or 10 is congruent to 1 mod 3
So we are not worried about how many times 3 divides 10 , but only in what the remainder will be after the division.
Now for a few pointers.

if a == b mod c then c divides a-b
b == b mod c
a.k == 0 mod a and a.k == 0 mod k
if a == b mod c then a+d == b+d mod c and a-d == b-d mod c
if a == b mod c then a.s == b.s mod c
if a == b mod c then a == b+k.c mod c for k>=0
if a == 1 mod c then aⁿ  == 1 mod c
if a == b mod c then a == b-c mod c or a == b+c mod c
if a == b mod c and d == e mod c then a+d == b+e mod c and a-d == b-e mod c
 

So how do we test for Proth primes? Lets use N = 641. We test if 641 = 5. 2⁷ + 1 is prime.
Lets choose a = 2 , Now N = 641, so N-1 = 640 , so (N-1)/2 = 320 = 5.2 ⁶ . So  a^(N-1)/2 = 2³²⁰ and now for the fun.

We have to test what is 2³²⁰ mod 641; if it is -1 then 641 is prime! But we may also try a =3,4,5,6,7 and so on.

1.  2^1 == 2 mod 641
2. Squaring we have 2^2 == 4 mod 641
3. Squaring we have 2^4 == 16 mod 641
4. Squaring we have 2^8 == 256 mod 641
5. Squaring we have 2^16 ==  256x256 == 65536 == 154 mod 641
6. Squaring we have 2^32 ==  154x154 == 23716 == 640 == -1 mod 641
3. Squaring we have 2^64 == -1x-1== 1 mod 641 (Note from here all squaring will have 1 as result)
5. Squaring we have 2^128 == 1 mod 641
5. Squaring we have 2^256 ==  1 mod 641
6. But 2^256 x 2^64 = 2^320 ==  1 x 1 == 1 mod 641

So a=2 does not prove 641 prime, but we see the trend in that the numbers we work with is never
bigger than the square of half of 640 and so by the way

2^320 = 2135987035920910082395021706169552114602704522356652769947041607822219725780640550022962086936576

Now lets try a=3

1.  3^1 == 3 mod 641
2. Squaring we have 3^2 == 9 mod 641
3. Squaring we have 3^4 == 81 mod 641
4. Squaring we have 3^8 == 6561 == 151 mod 641
5. Squaring we have 3^16 ==  151x151 == 22801 == 366 mod 641
6. Squaring we have 3^32 ==  366x366 == 133956 ==  628 == -13 mod 641
3. Squaring we have 3^64 == -13x-13== 169 mod 641
5. Squaring we have 3^128 == 169x169== 28561==357 mod 641
5. Squaring we have 3^256 ==  357x357==127449==531==110 mod 641
6. But 3^256 x 3^64 = 3^320 == 110x169==18590==640== - 1 mod 641

So in 6 steps we have proven 641 prime by using a=3. In ordinary prime testing we would have had to divide 641 by
3,5,7,11,13,17,19 and so on. This method is therefore much shorter and our numbers we work with is never bigger than
the square of half the number we test for prime ness. This procedure is also easily implemented in a program.

There you have it. Go and play.

Back to main page