<s>[INST] Prove That $3^n + 8^n$ is Not Divisible by $5$ (Using Induction) Prove that $3^n+8^n$ is not divisible by 5.
I know that this can be proved by using congruence and I am providing the proof by congruence below. But is there any way to Prove It By Induction.
The proof by congruence goes like this:
$3\equiv 3\pmod 5 \\ 3^2 \equiv 4\pmod 5 \\ 3^3\equiv 7\pmod 5 \\ 3^4\equiv 1\pmod 5 \\ 3^5\equiv 3\pmod 5$
Also,
$8\equiv 3\pmod 5 \\ 8^2 \equiv 4\pmod 5 \\ 8^3\equiv 7\pmod 5 \\ 8^4\equiv 1\pmod 5 \\ 8^5\equiv 3\pmod 5$
Adding the congruence up (since the same cycle repeats after the 4th power) none of them are divisible by 5 or equal to 0.
But I need a proof by Induction.
Any help will be appreciated.
 [/INST] Yes, you can do it by induction as well. Note that:
$3^{n+1}+8^{n+1}=3^n\times 3+8^n\times (3+5)=(3^n+8^n)\times 3+5\times 8^n$
By induction hypothesis the first term is not divisible by $5$ while the second term is obviously divisible by $5$. The required result follows. 
</s>