## Monday Math 97

Let $k=2^n+1$, n a positive integer. If k is prime (an odd prime, as k>2), show that n must be a power of two.

Let n be a positive integer but not a power of 2. Then it must have at least one prime factor that is not two, and thus must have at least one odd factor greater than 1. So let n=ab, with b>1 odd; we see 1≤a<n and 1<bn.

Now, recall that for integers x and y and odd positive integer m, that $x^m+y^m$ is divisible by the integer x+y. Letting y=1, we see $x+1|x^m+1$.
Substituting $x=2^a$ and m=b (as b is odd), we see
$\begin{array}{rcl}2^a+1&|&(2^a)^b+1\\2^a+1&|&2^{ab}+1\\2^a+1&|&2^{n}+1\\2^a+1&|&k\end{array}$,
and since 1≤a<n, $1<2^a+1<2^n+1=k$, we see that k has a factor $2^a+1$ which is neither unity nor k itself. Thus, if n is not a power of 2, then k cannot be prime. So if k is prime, n is a power of 2.

The numbers $F_n=2^{2^n}+1$ are known as Fermat numbers. The first few Fermat numbers are:
$F_0=2^{1}+1=3$
$F_1=2^{2}+1=5$
$F_2=2^{4}+1=17$
$F_3=2^{8}+1=257$
$F_4=2^{16}+1=65537$
$F_5=2^{32}+1=4294967297$

Those Fermat numbers which are prime are called Fermat primes. So our proof was that every prime of the form $2^n+1$ is a Fermat prime. Of the above list of Fermat numbers, F0, F1, F2, F3, and F4 are prime, but F5=4,294,967,297=641×6,700,417 is not prime. In fact, F0, F1, F2, F3, and F4 are the only known Fermat primes. However, as the Fermat numbers grow so rapidly, little is yet known about those for large n, and there are a number of open problems, including whether there are any other Fermat primes besides those listed above, and if there are infinitely many or finitely many Fermat primes (see here).