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