$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.
 A: 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$.)
A: $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$.
A: 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)$.
A: 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$

