# $2^{2^n}+5^{2^n}+7^{2^n}$ is always divisible by $39$

This problem is really bothering me for some time, I appreciate if you have some idea and insight.

Prove that

$$2^{2^n}+5^{2^n}+7^{2^n}$$

is divisible by $39$ for all natural numbers $n$.

There was a suggestion that this should be done by mathematical induction, however, with a twist, but I could not see what the twist is.

## 4 Answers

You first find $2^2$, $5^2$ and $7^2$, $\mod 39$, to be $4$, $25$ and $10$ respectively. These add to $39$.

Their squares are $16$, $1$, and $22$, which also add to $39$. This is power $2^2$.

The squares of these are $22$, $1$, $16$, which is the same as before, Thus if it is true for $2^n$, it's true for $2^{n + 1}$.

therefore $2^a + 5^a + 7^a$ is a multiple of $39$ if $a = 2^n$ (it's actually a multiple if $a \mod 12 = 4, 8$.)

$2^{2^{n+1}}=2^{2^n2}=(2^{2^n})^2$ so each term in this sequence is the square of the previous one.
Look at the remainders when you divide them by $13$: $$2^{2^1}=4\\ 2^{2^2}=4^2=16=3\pmod{13}\\ 2^{2^3}=3^2=9\pmod{13}\\ 2^{2^4}=9^2=81=3\pmod{13}$$ So the remainders repeat after that, and are $4,3,9,3,9,3,9$.
Do the same thing for $5^{2^n}$ and $7^{2^n}$, and for the remainders modulo $3$.

Here is an alternate approach.

As $3$ and $13$ are prime, it follows that for any $a$ not divisible by $3$ and $13$ we have $$a^2 \equiv 1 \pmod{3}$$ $$a^{12} \equiv 1 \pmod{13}$$

From the first one you get immediately that $a^{2^n} \equiv 1 \pmod{3}$ for $a \in \{ 2,5,7 \}$.

The second one implies that $$a^{16} \equiv a^{4} \pmod{ 13} \, \mbox{ for } a \in \{ 2,5,7 \} \,.$$

Therefore, for all $n \geq 1$ we have $$(a^{16})^{2^{n-2}} \equiv (a^{4})^{2^{n-2}} \pmod{ 13} \, \mbox{ for } a \in \{ 2,5,7 \} \,.$$ or $$a^{2^{n+2}} \equiv a^{2^{n}} \pmod{ 13} \, \mbox{ for } a \in \{ 2,5,7 \} \,.$$

Hence

$$2^{2^n}+5^{2^n}+7^{2^n} \equiv 2^{2^{n+2}}+5^{2^{n+2}}+7^{2^{n+2}} \pmod{13}$$

This is the inductive step $P(n) \Rightarrow P(n+2)$, you need to check $P(1), P(2)$.

Following similar patterns of proof from other answers, one can also prove:

• $2^{2^n}+3^{2^n}+5^{2^n}$ is always divisible by $19$
• $2^{2^n}+4^{2^n}+6^{2^n}$ is always divisible by $7$
• $3^{2^n}+4^{2^n}+7^{2^n}$ is always divisible by $37$