<s>[INST] Proving divisibility by $9$ for $10^n + 3 \times 4^{n+2} + 5$. I am trying to prove that for all $n$, $9$ divides $10^n + 3 \times 4^{n+2} + 5$. I first tried induction on $n$, but couldn't get anywhere with the induction step. I then tried to use modular arithmetic. The furthest I could get was:

As $10 \equiv 1 \mod 9$, $10^n \equiv 1^n = 1$ for all $n$, so modulo $9$, we have
\begin{align*}
10^n + 3 \cdot 4^{n+2} + 5 & = 3 \cdot 4^{n+2} + 6 \\
& = 3\left(4^{n+2} + 2\right) \\
& = 3\left(\left(2^2\right)^{n+2} + 2 \right) \\
& = 3\left(2^{2(n+2)} + 2 \right) \\
& = 3\left(2\left(2^{2(n+2) - 1} + 1\right) \right)
\end{align*}

I need to something get a factor of $3$ to show that the entire expression is divisible by $9$ and hence equal to $0$, mod $9$. But, with a sum of even terms, this does not appear possible.
Any hints on how to proceed would be appreciated. Is induction the standard way to prove something like this?
 [/INST] One way that is bound to succeed is to notice that this expression depends only on $n\bmod \varphi(9)$, which is $6$. This is because if $n\equiv m \bmod \varphi(9)$ then $10^n \equiv 10^m$ and $4^{n+2} \equiv 4^{m+2}$. This is a consequence of euler's theorem, so this would allow us to only need to check $6$ values.
</s>