Proving $19 \mid 2^{2^n} + 3^{2^n} + 5^{2^n}$ Theorem. $19 \mid 2^{2^n} + 3^{2^n} + 5^{2^n}$, for all positive integers $n$.

I'm tasked with proving the given theorem by induction. Here's where I've gotten so far...
Proof. Clearly, the theorem is true for $n=1$, establishing the base case. Moreover, it can easily be shown that the theorem works for $n=2,3,4,5,\ldots, 18$.
Suppose, now, that $k$ is an integer for which the given theorem holds. Consider, then, $k+18$.
$$2^{2^{k+18}} + 3^{2^{k+18}} + 5^{2^{k+18}}$$
By Fermat's Little Theorem, if $n \equiv m \pmod{p-1}$, then $a^m \equiv a^n \pmod{p}$. Clearly, $k+18 \equiv k \pmod{18}$. Then,
$$2^{2^{k+18}} \equiv 2^{2^k} \pmod{19}$$
$$3^{2^{k+18}} \equiv 3^{2^k} \pmod{19}$$
$$5^{2^{k+18}} \equiv 5^{2^k} \pmod{19}$$
Hence, $2^{2^{k+18}}$ may be expressed as $\;2^{2^k} + 19n$ for some integer $n$, $\;3^{2^{k+18}}$ as $\;3^{2^k}+ 19m$ for some integer $m$, and $\;5^{2^{k+18}}$ as $\;5^{2^k} + 19q$ for some integer $q$.
Thus, $2^{2^{k+18}} + 3^{2^{k+18}} + 5^{2^{k+18}} = (2^{2^{k}} + 3^{2^{k}} + 5^{2^{k}}) + 19(m+n+q)$, a sum of integers divisible by $19$, and thus clearly divisible by $19$.
By the principle of induction, we've thus shown that $19 \mid 2^{2^n} + 3^{2^n} + 5^{2^n}$, for all positive integers $n$, concluding the proof.
$\blacksquare$

Is this approach valid?
 A: Your approach seems valid, but, rather than checking $18$ cases,
you could note that $a^{2^7}=a^{128}=(a^{18})^7a^2\equiv a^2\bmod19$ when $\gcd(a,19)=1$,
so $a^{2^8}=(a^{2^7})^2\equiv a^{2^2},$ etc., so you would have to check only $n=1,2,3,4,5,6.$
A: The direct approach uses $-3\equiv 2^4\pmod{19}$ and $-5\equiv 2^{7}\pmod{19}.$
So when $n>0,$ $(-3)^{2^n}=3^{2^n}$ and $(-5)^{2^n}=5^{2^n},$ and we get:
$$2^{2^n}+3^{2^n}+5^{2^n}\equiv 2^{2^n}+\left(2^{2^{n}}\right)^4+\left(2^{2^{n}}\right)^{7} \pmod{19}$$
So the right hand side is $p(2^{2^n})$ where $$p(x)=x^7+x^4+x=x(x^6+x^3+1).$$
Now, it turns out that $2^{2^n}$ is always a root of $q(x)=x^6+x^3+1,$ modulo $19.$
Specifically, since $$q(x^2)=x^{12}+x^6+1=q(x)(x^6-x^3+1),$$
if $x$ is a root of $q$ then $x^2$ is a root of $q.$
So if $x=2^{2^n}$ is a root of $p(x),$ then so is $\left(2^{2^n}\right)^2=2^{2^{n+1}}$ is a root of $p(x).$
So we only need to deal with the case $n=1.$

At heart, what is happening is that the roots of $x^6+x^3+1$ are the primitive 9th roots of $1.$ That is:
$$\frac{x^9-1}{x^3-1}=x^6+x^3+1$$
Squaring a primitive 9th root of $1$ yields another primitive ninth root of $1.$
We can do examples of the same sort, modulo $37,$ such as:
$$37\mid 3^{2^n}+4^{2^n}+ 7^{2^n}$$
Here, $4^4\equiv -3, 4^7\equiv -7\pmod{37}.$
Other cases:
$$73\mid 2^{2^n}+16^{2^n}+18^{2^n}\\
109\mid 4^{2^n}+34^{2^n}+38^{2^n}$$
A: I don't think it's valid.  $k \equiv k + 18 \pmod {18}$ so $2^k \equiv 2^{k+18} \pmod {19}$.  And that means $a^{2^k} \equiv a^{2^{k+18}} \pmod m$ for an $m$ where $\phi(m) = 19$ and $\gcd(a,m) =1$ but... that doesn't work for  $a^{2^{k+18}}\equiv a^{2^k} \pmod {19}$
But you could be onto something.
$2^{k}\pmod{18}$ cycles.  $\phi 9 = 6$ so $2^{k+ 6} \equiv 2^k \pmod 9$ and $2^m \equiv 0 \pmod 2$ so for $k \ge 1$ we know $2^{k+ 6}\equiv 2^k$ and so $a^{2^{k+6}}\equiv a^{2^{k}} \pmod {19}$.
So we can do $6$ base cases.  Easier than $18$.
For $k = 1, ....6$ we have $2^k \equiv 2, 4,8,16, 14, 10 \pmod {18}$ and
But we can do better.
$2^2\equiv 4; 2^4 \equiv 16\equiv -3; 2^8 \equiv 9 \equiv 3^2\pmod {19}$
$3^2 \equiv 9; 3^4 \equiv 81 \equiv 5; 2^8 \equiv 5^2\pmod {19}$.
And $5^2 \equiv 6; 5^4 \equiv 36 \equiv -2$ and $5^{8}\equiv 2^2\pmod {19}$.
SO for $k \ge 1$ we have
$2^{2^{k+2}} + 3^{2^{k+2}} + 5^{2^{5+2}} \equiv 3^{2^k} + 5^{2^k} + 2^{2^k}\equiv 2^{2^k} + 3^{2^k} + 5^{2^k}\pmod {19}$
So we just need 2 base cases:
$2^2 + 3^2 + 5^2 \equiv 4+9 + 6 \equiv 0 \pmod {19}$
$2^{2^2} + 3^{2^2} + 5^{2^2} \equiv 16 + 81 + 36 \equiv -3+5 -2\equiv 0 \pmod{19}$
That's it.
A: Note that incrementing $n$ just corresponds to squaring each summand.  Just compute the first few cases mod 19 and look for a pattern:

*

*For $n=1$, we have $2^2 \equiv 4$, $3^2\equiv 9$, $5^2 \equiv 6$.  We are good since $4+9+6\equiv 19$.

*For $n=2$, we have $2^3=4^2 \equiv -3$, $3^3=9^2 \equiv 5$, $5^3\equiv 6^2 \equiv -2$.  Good again since $-3+5-2 \equiv 0$.

Now note that squaring the summands of the $n=2$ case will just give us the $n=1$ case again, as the numbers are the same as what we started with (2, 3, and 5) up to signs.  So subsequent increments of $n$ will just cause the summands to alternate between {4, 9, 6} and {-3, 5, -2}.  So we're done.
