Friday, April 04, 2008

Fermat Numbers

While of all Pierre de Fermat's proposed theorems really turned out to be theorems, not all of his conjectures turned out to be true.

In all fairness to Fermat, these theorems and conjectures were published after his death and were based on the notes he kept.

Pierre de Fermat conjectured that the Fn = 22n + 1 is prime for every integer n. These values Fn are today called Fermat Numbers.

The content in today's blog is taken from Jean-Pierre Tignol's Galois' Theory of Algebraic Equations.

Now, for n=0, 1, 2, 3, 4 the results are F0=3, F1=5, F2=17, F3=257, and F4=65537 which are all prime.

In 1732, Leonhard Euler showed that F5 = 641*6,700,417.

Since then, it has been shown that for 5 ≤ n ≤ 16, Fn is not prime.

Despite all these efforts, no other Fermat number has been found to be prime and no proof has been offered that would resolve this issue.

I will end today's blog with the following proof:

Lemma 1: If a prime number p has the form 2m + 1, then m is a power of 2.


(1) Assume that m is not a power of 2.

(2) Then it is divisible by some odd integer k.

(3) Now, we know that:

xk + 1 = (x + 1)(xk-1 - xk-2 + ... - x + 1) [See Lemma 4, here where a=x, b=1]

(4) Let x= 2m/k

(5) This then gives us:

(2m/k)k + 1= (2m/k + 1)([2m/k]k-1 - [2m/k]k-2 + ... - [2m/k] + 1)

(6) Since (2m/k)k + 1 = 2m + 1, it follows that 2m + 1 cannot be a prime since it is divisible by (2m/k + 1).

(7) Therefore, we have a contradiction and we reject our assumption in step #1.