Using Fermat Number to prove the infinity of primes

What is Fermat Number?

Fermat number is defined as 2^(2^n)+1 (named after Pierre de Fermat) where n is a non-negative integer. The first five Fermat numbers are 3, 5, 17, 257 and 65537.

We denote F(n) = 2^(2^n)+1 for convenience. So,

F(0) = 2^2⁰+1 = 3

F(1) = 2^2¹+1 = 5

F(2) = 2^2²+1 = 17

F(3) = 2^2³+1 = 257

F(4) = 2^2⁴+1 = 65537

Lemma 1: (F(m)−2) is divisible by F(n) if m > n.

Proof:

F(m)−2

= 2^(2^m)−1

= {2^[2^(m−1)]+1}×{2^[2^(m−1)]−1}

=F(m−1)×[F(m−1)−2]

Similarly, F(m−1)−2 = F(m−2)×[F(m−2)−2]

Hence, we can deduce that

F(m)−2

=F(m−1)×[F(m−1)−2]

=F(m−1)×F(m−2)×[F(m−2)−2]

=F(m−1)×F(m−2)××F(n)×[F(n)−2]

So, (F(m)−2) is divisible by F(n) if m > n.

Lemma 2: F(m) and F(n) are relatively prime if m≠n. (That means their greatest common divisor is 1)

Proof:

Assume m > n, and let g be the greatest common divisor of F(m) and F(n).

So, g|F(m) & g|F(n)

(g|F(m) means g divides F(m) OR F(m) is divisible by g)

The fact that g|F(n) and by lemma 1, F(n)|[F(m)−2], g|[F(m)−2]

So, g|{F(m)−[F(m)−2]} and thus g|2

i.e. g = 1 or 2

But all Fermat numbers are odd, therefore g must be 1.

Hence, F(m) and F(n) are relatively prime if m is not equal to n.

Final deduction

Now, to prove the infinity of primes, we keep generating Fermat numbers F(n). If F(n) is prime, we have a new prime number. If F(n) is composite, then it has a prime factor which never exists before since all distinct Fermat numbers are relatively prime (by lemma 2). As we can generate as many Fermat numbers as we want by simply substituting different values of n , so the number of primes is infinite.