Fermat Numbers
Created | Updated Jan 12, 2012
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+1 | 2 | prime |
| 21+1 | 3 | prime |
| 22+1 | 5 | prime |
| 23+1 | 9 | composite = 32 |
| 24+1 | 17 | prime |
| 25+1 | 33 | composite = 3 x 11 |
| 26+1 | 65 | composite = 5 x 13 |
| 27+1 | 129 | composite = 3 x 43 |
| 28+1 | 257 | prime |
| 29+1 | 513 | composite = 33 x 19 |
| 210+1 | 1025 | composite = 52 x 41 |
| 211+1 | 2049 | composite = 3 x 683 |
| 212+1 | 4097 | composite = 17 x 241 |
| 213+1 | 8193 | composite = 3 x 2731 |
| 214+1 | 16385 | composite = 5 x 3277 |
| 215+1 | 32769 | composite = 32 x 11 x 331 |
| 216+1 | 65537 | prime |
| 217+1 | 131073 | composite = 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 + 1These 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.
