infinitudeoffermatprimes

Infinitude of Fermat Primes

There are an infinite number of Fermat primes (2**(2**n)-1).

Proof:

Suppose Fn = 2**(2**n)-1

hcf (Fn, m) = 1, for all m<n [by Lemma 1]

let n->99999… [Euclid]

=> Fn prime

=> there exist an infinite number of prime Fn

LEMMA 1

Any divisor of Fn is of the form 2**(n+1)k+1

Proof:

Suppose p | Fn, i.e. 2**(2**n) == -1 [mod p]

Let 2 have order h modulo p

2**(2**(n+1)) == 1 [mod p]

i.e. h | 2**(n+1) [by Lemma 2]

Also, 2**(2**n) <> 1 [mod p], so h doesn’t divide 2**n [by Lemma 2]

=> h=2**(n+1)

But, 2**(p-1) == 1 [mod p] [Fermat’s Little Theorem]

So, h | p-1 [by Lemma 2]

i.e. 2**(n+1) | p-1

or p = 2**(n+1)k + 1

LEMMA 2

Definition:

The order of a modulo n is the smallest positive integer k, s.t. a**k == 1 [mod n]

Let a have order k mod n, then a**h == 1 [mod n] <=> k | h

Proof:

Suppose k | h, i.e. h = jk, then

a**k == 1 => a**h == 1 [mod n]

Conversely,

Suppose a**h == 1 [mod n]

h = qk + r [0 <= r < k]

a**h == a**(qk+r) == (a**k)**q.a**r

=> a**r == 1

=> r = 0; otherwise k is not the smallest integer such that a**k == 1

Therefore, h = qk, i.e. k | h