Proving $2^{2^n}+3^{2^n}+5^{2^n}$ is divisible by $19$ for all $n\geq 1$ by induction

Question

I came across the following in the book Handbook of Mathematical Induction: $$ 19\mid (2^{2^n}+3^{2^n}+5^{2^n}),\quad n\in\mathbb{Z^+}\tag{1} $$ Apparently, this problem is not so bad if you think about it in a somewhat "outside of the box" sort of way, but it is supposed to be quite challenging otherwise.

Question: How might one prove $(1)$ using induction or otherwise? The "outside of the box" answer has been provided but with details oranged out so as not to spoil it for anyone who may come up with that solution individually.

Answer 1

For $n\geq 1$, let $S(n)$ denote the claim $$ S(n) : 19\mid (2^{2^n}+3^{2^n}+5^{2^n}),\quad n\in\mathbb{Z^+} $$ Base step: For $n=1, S(1)$ says that $19\mid 38$ which is true because $38=2\cdot 19$. Also, for $n=2, S(2)$ says that $19\mid 722$ which is true because $722=38\cdot 19$.

Inductive step: Fix some $k\geq 1$ and suppose...

... that $S(k)$ and $S(k+1)$ are true. To see that $S(k+2)$ follows [Note: An alternative form of mathematical induction is being employed here.], note the following concerning $S(k+2)$: $$\small 2^{2^{k+2}}+3^{2^{k+2}}+5^{2^{k+2}}= 2^{4\cdot 2^k}+3^{4\cdot 2^k}+5^{4\cdot 2^k}=16^{2^k}+81^{2^k}+625^{2^k}= 3^{2^k}+5^{2^k}+2^{2^k}\pmod{19}.$$ Thus, by the inductive hypothesis, $S(k+2)$ follows. This completes the inductive step.

By mathematical induction, for all $n\geq 1, S(n)$ is true. $\blacksquare$

Answer 2

Solution without induction

Let $f(n)=2^n+3^n+5^n$, we know that $2^6\equiv 3^6\equiv 5^6\equiv 7\mod 19$, so for every integer $n=6k+r$ with $r=0,\cdots,5$ we have: $$f(n)=f(6k+r)\equiv 7^k f(r) \mod 19\tag1$$

and given an integer $m\in \Bbb Z^+$ we have :$$2^m\equiv 2 \text{ or } 4\mod 6\tag{2}$$

from $(1)$ and $(2)$ it suffices to prove that $19$ divides $f(2)$ and $f(4)$.