<s>[INST] Induction proof: $2^n + 3^n ≡ 5^n (mod 6)$ I'm trying to prove that $2^n + 3^n ≡ 5^n\ (mod\ 6)$ using induction.
$n=1$:
$2+3≡5\ (mod\ 6)$
$n=k$:
$2^k + 3^k ≡ 5^k\ (mod\ 6)$
$n=k+1$:
$2^{k+1} + 3^{k+1} ≡ 5^{k+1}\ (mod\ 6)$
$2*2^k + 3*3^k ≡ 5*5^k\ (mod\ 6)$
$6\ |\ 5*5^k - 2*2^k - 3*3^k$
$6\ |\ (2+3)*5^k - 2*2^k - 3*3^k$
$6\ |\ 2*5^k + 3*5^k - 2*2^k - 3*3^k$
$6\ |\ 2*(5^k - 2^k) + 3*(5^k - 3^k)$
Not quite sure if I'm going in the right direction or where to go from here...
 [/INST] Once you check for $n=1$, you want to show: for $k\geq 1$,
$$
2^k + 3^k ≡ 5^k\pmod{6}\quad\text{implies}\quad 2^{k+1} + 3^{k+1} ≡ 5^{k+1}\pmod{6}. 
$$
So start with $2^k + 3^k ≡ 5^k\pmod{6}$. This implies we can write $5^k=2^k+3^k-6m
$ for some integer $m$. Proceeding from here, we have
\begin{align*}
5^{k+1}=5(2^k+3^k-6m)&=2^{k+1}+3\cdot2^k+3^{k+1}+2\cdot 3^k-30m\\
&=2^{k+1}+3^{k+1}+6(2^{k-1}+3^{k-1}-5m)
\end{align*}
which indeed implies $2^{k+1} + 3^{k+1} ≡ 5^{k+1}\pmod{6}$.
</s>