Fermat number

A number of the form 2²ⁿ + 1, for any natural number n, sometimes denoted as F_n. The first five (3, 5, 17, 257 and 65537) are primes, and some people accuse Pierre de Fermat of claiming that all such numbers were prime.

Of course, the general consensus used to be that this was true, until 1732, when Leonhard Euler discovered that 2^32 + 1 can be expressed as 641 * 6700417. In 1880, a retired mathematician named Landry discovered that 2^64 + 1 = 274177 * 67280421310721. In 1970, John Brillhart (my math professor) and his associate Morrison discovered that 2^128+ 1 = 59649589127497217 * 5704689200685129054721. After that, the prime factors start to get incredibly large. It is now highly suspected that all Fermat numbers greater than F₄ are composite; the smallest Fermat number whose primality is unknown is presently 2^(2^31) + 1. The largest prime factor for a Fermat number was recently discovered by John Cosgrave and Yves Gallot on July 23, 1999: They found that the prime number 3*2^382449+1 divides the Fermat number 2^(2^382447) + 1.

Detailed information on the Cosgraves-Gallot discovery can be found at:
http://perso.wanadoo.fr/yves.gallot/papers/nlkff.html

The present status of the Fermat numbers can be attained by directing your internet browsing software to:
http://www.prothsearch.net/fermat.html

The Fermat numbers (F(n)=2^(2^n)+1) are pairwise relatively prime; in other words, each Fermat number is coprime with all the others. The first observation to be made from this is that there must be an infinite number of primes, since every new Fermat number (and there are an infinite number of those anyways) shares no factors with any other. The second observation that I have is, "Wow. These numbers increase fast." Essentially, the number of binary digits doubles in going from one Fermat number to the next. The same is (roughly) true of the number of decimal digits (after F(3)).

Proof that the Fermat numbers are relatively prime:
Begin with the first Fermat number, F(0)=3. This just so happens to equal the Mersenne prime 2^2-1=3. Note that the second Fermat number, F(1)=5, is equal to 2^2+1. 3 and 5 are both prime, and are automatically coprime. (x+1)*(x-1)=x^2-1, so 3*5=(2^2-1)*(2^2+1)=2^4-1=15. F(2)=17=2^4+1, so 3*5*17=(2^4-1)*(2^4+1)=2^8-1=255. F(3)=2^8+1=257 (just so the pattern is obvious...). Now for some induction on the hypothesis that "the multiplication of the first k Fermat numbers is equivalent to F(k)-2":
  i) Show for k=1 (done above).
  ii) Assume for k=m, m an abitrary natural number. So F(0)*F(1)*F(2)*...*F(m-1)=F(m)-2 (by assumption).
  iii) Try k=m+1. We expect that F(0)*F(1)*...*F(m-1)*F(m)=F(m+1)-2. Substituting from the assumption, F(0)*F(1)*...*F(m-1)*F(m)=(F(m)-2)*F(m)=(2^(2^m)-1)*(2^(2^m)+1)=2^(2^(m+1))-1=F(m+1)-2, which is what we expected. Therefore the hypothesis is true.
The consequence of the above induction is that every Fermat number is congruent to 2 mod every smaller Fermat number. 2 is the only number that could divide both of the numbers x and x+2, but every Fermat number is odd, so all Fermat numbers are relatively prime.