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

Prove that


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.


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


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

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.