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