# Prove by Induction $19^{n}-4^{2n}$ is divisible by 3

Assume $$n=0$$ for $$19^{n}-4^{2n}$$

Just going to do some simplification first: $$19^{n}-4^{2n}\implies19^{n}-16^{n}$$ and if $$n=0$$ then $$19^{0}-16^{0}$$ then it is zero which is obviously divisible by 3.

Now for the inductive hypothesis $$19^{n}-16^{n}\mod{3}=0$$

So now I show it for the case $$n+1$$ and one gets: $$19^{n+1}-16^{n+1}\implies19^{n}\cdot19-16^{n}\cdot16$$ but from here how do I show divisibility by 3?

• Make the appropriate modifications to the answer over here, or over here. Also see the questions linked to the first of these. Commented May 24, 2023 at 13:42
• Try this: $a^{n+1}-b^{n+1}=(a+b)(a^n-b^n)-ab(a^{n-1}-b^{n-1})$, and from case $n-1$, $n$ prove the case $n+1$ Commented May 24, 2023 at 13:44
• With $f(n)=19^{n}-4^{2n}$. we get $f(n+1)-f(n)=3 \cdot ( 6 \cdot 19^n-5 \cdot 4^{2n})$
– lhf
Commented May 24, 2023 at 16:35

Let $$19^n-16^n=3k$$ then $$19^{n+1}-16^{n+1}$$ $$=19^n\cdot19-16^n\cdot16$$ $$=(3k+16^n)19-16^n\cdot16$$ $$=57k+19\cdot16^n-16\cdot16^n$$ $$=57k+3\cdot16^n$$ $$=3\lambda$$
• Third step is a bit confusing: $19^{n}\cdot19\implies(3k+16^{n})19$ Commented May 24, 2023 at 13:46
• I assumed that $19^n-16^n=3k$ then adding $16^n$ to both sides of this equation yeilds $19^n=3k+16^n$ and I substituted this value in the third step Commented May 24, 2023 at 13:51
So you’re off to a good start. The next step is just to realize that $$19-16=3$$, which is the reason this is true at all.
So you have: $$19(19^n) - 16(16^n) = (16+3)19^n - 16(16^n) = 16(19^n - 16^n)+3(19^n)$$
Now from your induction assumption $$(19^n - 16^n)$$ is a multiple of 3, and $$3(19^n)$$ is clearly a multiple of 3. You’re adding two multiples of 3, the result is a multiple of 3