1
$\begingroup$

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?

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

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}$.

$\endgroup$
2
$\begingroup$

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$.

Hope that helps,

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – user95864
    Jul 24 '15 at 9:41
  • $\begingroup$ @user95864 : Yes, that's it! $\endgroup$ Jul 24 '15 at 14:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.