# Prove that there are infinitely many composite numbers of the form $2^{2^n}+3$.

There are infinitely many composite numbers of the form $2^{2^n}+3$. [Hint: Use the fact that $2^{2n}=3k+1$ for some $k$ to establish that $7\mid2^{2^{2n+1}}+3$.]

If $p$ is a prime divisor of $2^{2^n}+3$ then $2^{2^n}+3\equiv0\pmod{p}$. But I don't think this is useful. I don't see how the fact that $2^{2n}=3k+1$ helps to show that $7\mid2^{2^{2n+1}}+3$.

Any hints on how to start solving this problem?

• If $2^{2n} = 3k+1$, what is $2^{2n+1}$? And how may that relate to $7$? Jul 23 '15 at 15:21

Let $a_n=2^{2^n}+3$. Then $a_{n+1}=(a_n-3)^2+3 = a_n^2-6a_n+12$. Since: $$p(x)=x^2-6x+12 \equiv (x-1)(x+2) \pmod{7}$$ maps $0$ to $5$ and $5$ to $0$, we have that $7\mid a_n$ iff $n$ is odd, since $a_1=7\equiv 0\pmod{7}$.
Let $p$ be a prime. Then by Fermat's little theorem, $2^{p-1} \equiv 1 \pmod{p}$, so $2^{k(p-1) +2} \equiv 4 \pmod p$. So we wish to find conditions on $n$ so that $2^n \equiv 2 \pmod{p-1}$. Now for $p=7$, $p-1 = 6$ and the sequence $2^n$ modulo $6$ looks like this, starting with $n=1$ : $$2, 4, 2, 4, 2, 4, \cdots$$ so for $n=2m+1$, $2^{2m+1} \equiv 2 \pmod 6$, which means $$2^{2^n}+3 \equiv 2^{2^{2m+1}} + 3 \equiv 2^2+3 \equiv 0 \pmod 7.$$ You should have just used the hint! But you asked the question here so I figured it didn't tell you much.
P.S. : If I used the hint a 100%, I would have written $2^{2m} = 3k+1$ which implies that $2^{2m+1} = 6k+2$, which is essentially my remark that $2^{2m+1} \equiv 2 \pmod 6$.
• It took some time, but I think I understand it now. So basically, we want to prove that $7|2^{2^n}+3$ for $n$ odd, so $7|2^{2^{2m+1}}+3$. From the fact that $2^{2m}=3k+1$, follows that $2^{2m+1}\equiv2\pmod{6}$. Finally, using Fermat, this gives then $2^{2^{2m+1}}+3\equiv2^{2}+3\equiv0\pmod{7}$. Am I correct? Jul 24 '15 at 9:41