Fermat Numbers Content from the guide to life, the universe and everything

Fermat Numbers

2 Conversations

Pierre de Fermat (1601 - 1665) was a French mathematician who laid the ground work for much of the branch of mathematics which is known today as Number Theory1. Armed with little more than the basics of arithmetic and algebra, Fermat and others like him came across many apparent facts about the whole numbers, which they attempted to prove. Fermat guarded his proofs carefully, because there was no system at the time of publishing new proofs, and he didn't want anyone stealing his proof and claiming the credit. Because of this it is not always clear what Fermat had proved and what he hadn't. His most famous assertion, which he claimed to have proved, became known as Fermat's Last Theorem. However, some apparently true facts evaded proof completely. One such is the study of the numbers now known as Fermat Numbers.

Fermat, like a lot of other mathematicians of the day, was interested in prime numbers. Among others, he studied the numbers which are one greater than a power of 2. He noticed that some of them are prime and some composite, and they seem to form a pattern.

20+12prime
21+13prime
22+15prime
23+19composite = 32
24+117prime
25+133composite = 3 x 11
26+165composite = 5 x 13
27+1129composite = 3 x 43
28+1257prime
29+1513composite = 33 x 19
210+11025composite = 52 x 41
211+12049composite = 3 x 683
212+14097composite = 17 x 241
213+18193composite = 3 x 2731
214+116385composite = 5 x 3277
215+132769composite = 32 x 11 x 331
216+165537prime
217+1131073composite = 3 x 43691

Fermat noticed that only the following exponents give a prime: 0, 1, 2, 4, 8, 16. With the exception of the 0, these are all themselves powers of 2. Fermat decided that he had stumbled on a formula which always produced prime numbers.

Fn = 22n + 1

These numbers are now known as 'Fermat Numbers'.

It is simple enough to prove that if x is not a power of 2, then 2x + 1 is not prime, but Fermat was unable to prove the converse, that if x is a power of 2, then 2x + 1 is a prime. The few values listed here show that it is certainly true for F0, F1, F2, F3 and F4.

The next such number is F5 which equals a massive 4,294,967,297. Fermat didn't know whether this was prime or not, as it is a very big number, with no obvious divisors such as 3 or 7.

It was not until the next century that Euler2 used more advanced mathematics to show that any factor of Fn must be one greater than a multiple of 2n+2. Using this fact to examine F5, he reduced the number of possible factors to a small list and quickly showed that 4,294,967,297 is in fact divisible by 641, a fact which anybody can check if they are capable of long division. So Fermat's formula for prime numbers turned out to be incorrect. One more of Fermat's many unproved assertions had been laid to rest, in this case with the result that Fermat was wrong.

Other Interesting Features of Fermat Numbers

It can be shown by a bit of clever algebra that the Fermat Numbers are pairwise relatively prime. That is, no two of them share any common factors. Pólya3 used this fact to prove that there are an infinite number of prime numbers, since every Fermat Number is either prime or has as a factor a prime which is not shared with any other Fermat Number.

The biggest Fermat Number for which a factor is known is F2145351. This number is unimaginably large, so big that even to write out the number of digits it has would take more ink than the entire matter in the visible universe! And yet mathematicians have shown that it is composite, and is divisible by 3*22145353 + 1, a number which is pretty small by comparison, having merely about 600,000 digits.

Further Information

For lots of interesting news and discoveries about Fermat Numbers, take a look at the website of John Cosgrave, the man who discovered the biggest known composite Fermat Number, in February 2003.

1Number Theory is the study of whole numbers, those without any fractional or decimal part.2Leonhard Euler, Swiss mathematician (1707-1783).3George Pólya, Hungarian-born US mathematician (1887-1985).

Bookmark on your Personal Space


Edited Entry

A998157

Infinite Improbability Drive

Infinite Improbability Drive

Read a random Edited Entry

Categorised In:


References

h2g2 Entries

External Links

Not Panicking Ltd is not responsible for the content of external internet sites

Write an Entry

"The Hitchhiker's Guide to the Galaxy is a wholly remarkable book. It has been compiled and recompiled many times and under many different editorships. It contains contributions from countless numbers of travellers and researchers."

Write an entry
Read more