Induction with divisibility QUESTION: Prove that $16 \mid 19^{4n+1}+17^{3n+1}-4$ for all $n \in \mathbb{N}$
This is what I have so far but I'm not sure where to go from here.
PROOF:
Let $16 \mid 19^{4n+1}+17^{3n+1}-4$ equal $S(n)$.
Base case, let $n=0$.
\begin{align*}
16 &\mid 191+171-4\\
  = 16 & \mid 32\\
  = 2
\end{align*}
Therefore, $S(0)$ is true.
Using induction hypothesis, suppose $19^{4k+1}+17^{3k+1}-4$ is divisible by $16$ for all $n \in \mathbb{N}$.
Claim,
$16 \mid 19^{4k+1}+17^{3k+1}-4$,
that is $19^{4k+1}+17^{3k+1}-4=16m$, whereby $m$ is a multiple of $16$.
The above equation simplifies into,
\begin{align*} 
16 & \mid 19^{4n+5}+17^{3n+4}-4\\
16 & \mid 19^4 \cdot 19^{4k+1} + 17^3 \cdot 17^{3n+1}-4
\end{align*}
photo of my working out

Q. Show that $16$ $|$ $19^{4n+1} +17^{3n+1} -4$ $\forall$ $ n \in \mathbb N$.
First of all, simplify the expression. Write $19=16+3$ and $17=16+1$, then use binomial theorem to expand it. That way you'll get a simpler expression to use induction.
$16$ $|$ $19^{4n+1} +17^{3n+1} -4 \implies$ $16$ $|$ $3^{4n+1}+1-4 \implies 16$ $|$ $3(3^{4n}-1)$
$\implies 16$ $|$ $3^{4n}-1$.
Method 1 to proceed:
Now here it's easier to just use the fact that $x-y$ $|$ $x^n-y^n$, because it will prove that $ 16$ $|$ $3^{4n}-1$ directly, without induction. ( As $16$ $|$ $3^4 -1$ $|$ $3^{4n}-1$. )
But if you wish to use induction only, then here it is:
Method 2 to proceed:
Let $P(n):16$ $|$ $3^{4n}-1$.
$P(1), P(2)$ are true.
Let $P(i)$ be true for $i=1,2,\cdots,k$
$16$ $|$ $3^{4n}-1 \implies 16$ $|$ $(3^{4n}-1)(3^4+1) \implies 16$ $|$ $3^{4n+4}-1 +3^{4}(3^{4n-4}-1)$
And we know $16 $ $|$ $(3^{4n-4}-1)$ (As $P(n-1)$ is true).
$\implies 16$ $|$ $3^{4n+4}-1 \implies P(n+1)$ is true, and hence $P(n)$ is true for all natural numbers $n$.
