$19 \mid 2^{2^{n}} + 3^{2^{n}} + 5^{2^{n}}$

Question

I tried to demonstrate the next equation is divisible by 19:

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

When $n$ is $1$:

$$ 2^{2^1} + 3^{2^1} + 5^{2^1} $$ $$ 4 + 9 + 25 = 38 $$

When $n$ is $k$:

$$ 2^{2^k} + 3^{2^k} + 5^{2^k} $$

Finally, when $n$ is $k+1$:

$$ 2^{2^{k+1}} + 3^{2^{k+1}} + 5^{2^{k+1}} $$

I try by expanding, by subtraction, but no solution /:

Answer 1

Not with induction:

The residues of each term cycle since $a^{2^{n+1}} = (a^{2^n})^2$

$2^{2^n} \pmod {19}$ with $4, 16, 9, 5, 6, 17, 4, \dots$

$3^{2^n} \pmod {19}$ with $9, 5, 6, 17, 4, 16, 9, \dots$

$5^{2^n} \pmod {19}$ with $6, 17, 4, 16, 9, 5, 6, \dots$

By adding terms pairwise, you can see that the statement is true. This also provides some motivation for induction using $k+6$ rather than $k+1$.

Answer 2

Hint: $$2^{n+6}+3^{n+6}+5^{n+6}=2^6\cdot2^n+3^6\cdot 3^n+5^6\cdot5^n\equiv7\cdot2^n+7\cdot3^n+7\cdot5^n\ \ (\text{mod }19)$$

What can $2^k\text{ mod }6$ be?

Answer 3

By Fermat's little theorem, if $n\equiv m\ \ \text{mod}\ (p-1)$, then $a^m \equiv a^n\ \ \text{mod}\ p$. Now, since any power of two modulo $18$ is one of the six numbers in $S=\{2,4,8,10,14,16\}$, it remains to check that: $$2^k+3^k+5^k \equiv 0 \ \ \text{mod}\ 19$$ For all $k\in S$.