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.

Proof:

(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.

QED

References

7 comments:

hanelifou said...

Small typo: You say F(sub n) = 2^(2^(n)) are Fermat primes, but I take it you mean F(sub n) = 2^(2^(n)) + 1.

Larry Freeman said...

Hi Hanelifou,

Thanks for noticing that. I've updated my blog entry. :-)

-Larry

Emac98 said...
This comment has been removed by the author.
Larry Freeman said...

Hi Emac,

According to wikipedia, it is true for 5 ≤ n ≤ 32.

Remember, F(16) = 2^(2^16) + 1 which is an odd number.

-Larry

neat_maths said...

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

I think you meant "No other Fermat NUMBER has been found to be prime"

Larry Freeman said...

Hi Neat Maths,

I agree with your suggestion.

I've updated the blog to use "Fermat Number" instead of "Fermat Prime".

-Larry

Unknown said...

Hello, I am new on this subject but I believe that I can prove that all the Fn>F4 are composites. Please let me know if someone else already proves this . If not please let me know how or where to submit my finding.
Thanks,
Mui Nguyen