How can I prove that $2^{2^x}+1$ is always prime?

Question

So the problem is that I have to prove that $2^y+1$ is prime if and only if $y$ is a power of $2$.

Answer 1

But:

• $$2^{2^5}+1=641\cdot6700417\ne\text{prime}$$
• $$2^{2^6}+1=274177\cdot67280421310721\ne\text{prime}$$
• $$2^{2^7}+1=59649589127497217\cdot5704689200685129054721\ne\text{prime}$$
• $$2^{2^8}+1\ne\text{prime}$$
• $$2^{2^9}+1\ne\text{prime}$$
• $$2^{2^{10}}+1\ne\text{prime}$$
• $$2^{2^{11}}+1\ne\text{prime}$$
• $$2^{2^{12}}+1\ne\text{prime}$$
• $$2^{2^{13}}+1\ne\text{prime}$$
• $$2^{2^{14}}+1\ne\text{prime}$$
• $$2^{2^{15}}+1\ne\text{prime}$$
• $$2^{2^{16}}+1\ne\text{prime}$$
• $$2^{2^{17}}+1\ne\text{prime}$$

Answer 2

Theorem: For $a^n+1$ to be prime, where $a>1$, $n$ has to be a power of $2$.

Proof: If $a=1$, then $a^n+1=2$. So take $a>1$. Now if $n$ is a positive integer, $$a^n-b^n=(a-b)\sum_{k=0}^{n-1} a^kb^{n-1-k}.$$ So if $n=rs$ with $1 \leqslant r < n$, $1 < s \leqslant n$ and $s$ odd, then since $(a-b)\mid(a^{rs}-b^{rs})$ on substituting $b=-1$, since $a>1$, $(a+1)>1$ also and $a^n+1$ is therefore composite. Hence, $n$ must be a power of $2$.

Q.E.D.

The converse, however, does not follow. Here are the first seven Fermat numbers, with their prime factorisations, where $p_{n}=$ $n$th prime number: \begin{align*} F_0&=2^{2^0}+1=3=p_{2},\\ F_1&=2^{2^1}+1=5=p_{3},\\ F_2&=2^{2^2}+1=17=p_{7},\\ F_3&=2^{2^3}+1=257=p_{55},\\ F_4&=2^{2^4}+1=65537=p_{6543}\\ F_5&=2^{2^5}+1=4294967297=641\cdot6700417=p_{116}\cdot p_{457523},\\ F_6&=2^{2^6}+1=18446744073709551617=274177\cdot67280421310721\\ &=p_{23974}\cdot p_{2184072078357}. \end{align*}

Here are some notes on the conditions prime factors of Fermat numbers follow:

Euler proved in 1770 that if $\gcd(a,b)=1$ then the factors of $a^{2n}+b^{2n}$ are either $2$ or of the form $2^{n+1}k+1$, whilst Lucas, in 1878, proved the prime divisors of $2^{2^n}+1$ must be of the form $2^{n+2}l+1$; we have then $641=2^{5+2}\cdot5+1$ and $6700417=2^{5+2}\cdot52347+1$. Euler was the first in 1732 to show $2^{2^5}+1$ is composite. He showed $5\cdot 2^7\equiv-1\pmod{641}$, so $5^4\cdot2^{28}\equiv 1\pmod{641}$, which as $5^4\equiv-2^2\pmod{641}$, $-2^{32}\equiv 1\pmod{641}$.

Euler proved that any prime factor of a Fermat number is of the form $64k+1$, $641$ being $64\cdot10+1$. Fermat would surely have kicked himself for missing such a small factor, which toppled one of his only mistaken conjectures, that all such numbers were prime! Indeed it is believed he may have found the 'factor' but made a mistake in ascertaining its primality as it is known he knew any factors had the form $64k+1$ of Euler.

M. Kraitchik showed the following: Since $641=5^4+2^4=5\cdot2^7+1$, we have $$2^{28}(5^4+2^4)=5^4\cdot2^{28}+2^{32},$$ $$(5\cdot2^{7}+1)(5\cdot2^{7}-1)(5^2\cdot2^{14}-1) =(5^2\cdot2^{14}+1)(5^2\cdot2^{14}-1)=5^4\cdot2^{28}-1,$$ hence $$5^4+2^4\mid 5^4\cdot2^{28}+2^{32}\quad\text{and}\quad 5\cdot2^7+1\mid 5^4\cdot2^{28}-1,$$ and so $641$ will divide the difference which is $F_5$, $$(5^4\cdot2^{28}+2^{32})-(5^4\cdot2^{28}-1)=2^{32}+1.$$

Except for the first five Fermat numbers, which are prime, no other Fermat number has been found to prime.

Answer 3

We want to prove that if $2^y+1$ is prime $\Rightarrow$ $y=2^k$.
Let $y$ be odd:
$2\equiv 2 \pmod 3,\ 2^2 \equiv 1 \pmod 3$. So $ 2^y+1 \equiv 0 \pmod 3.$
Let $y$ be even:
$y= 2^kl $ where $l$ is an odd number. Now if $l >1,$
$$2^{2^kl}+1\equiv 2^l 2^{2^k}+1\equiv 1.2+1\equiv0\pmod 3.$$ Therefore $y=2^k$.