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
 A: 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$.
A: $\!\bmod 16\!:\ \color{#c00}{19^{4n}}\equiv 3^{4n}\equiv (3^4)^n\equiv 1^n\!\equiv\color{#c00}1,$ and $\,\color{#0a0}{17^k}\equiv 1^k\!\equiv\color{#0a0}1\,$ by CPR = Congruence Power Rule,
hence $\,19(\color{#c00}{19^{4n}})+\color{#0a0}{17^{4n+1}}\!-4\equiv 19(\color{#c00}{1})+\color{#0a0}1-4\equiv 0.\,$ CPR has a short and simple inductive proof (simply iterate the Congruence Product Rule).
Or w/o mod: $ $ it is $\,19(\color{#c00}{19^{4n}-1)} + \color{#0a0}{17^n\!-\!1} + 16\,$ and $\,16\mid \color{#0a0}{17^n\!-\!1}\,$ by FT = Factor Theorem, and $\,\color{#c00}{19^{4n}\!-\!1} = 19^{4n}-3^{4n}+\color{#90f}{3^{4n}\!-\!1}\,$ and by FT: $\,19\!-\!3\mid 19^{4n}\!-\!3^{4n},\,$ $\,16\mid 3^4\!-\!1\mid \color{#90f}{3^{4n}\!-\!1}.\,$ Again FT has a short simple inductive proof: hint $\,a^{n+1}\!-\!b^{n+1} = (a\!-\!b)a^n +b(a^n\!-\!b^n)$.
Note how the above divisibilities are essentially proving the same congruences as above, but in a more cumbersome way due to use of relations (divisibility) vs. operations (arithmetic $\!\bmod 16$)
Remark $ $ Just as above, generally using congruences makes inductions like this very easy, reducing them to trivialities like $\,a\equiv 1\Rightarrow\, a^n\equiv 1,\,$ as explained at length in many prior answers, e.g. here and here and here. This innate arithmetical (power) structure is usually greatly obfuscated in direct inductive proofs - which often greatly complicates the discovery (and comprehension) of the key inductive step
A: To show $16  \mid 19^4 \cdot 19^{4k+1} + 17^3 \cdot 17^{3n+1}-4$ given $16 \mid 19^{4k+1}+17^{3k+1}-4$, note that
$19^4 \cdot 19^{4k+1} + 17^3 \cdot 17^{3n+1}-4=$
$17^3\color{blue}{(19^{4k+1}+17^{3n+1}-4)} + \color{blue}{(19^4-17^3)}\cdot19^{4n+1}+
\color{blue}{(17^3\cdot4-4)},$
and all of the blue terms are divisible by $16$.
