Prove that $5^n \equiv 8n^2-4n+1 \mod 64$ using induction I am trying to prove that $5^n \equiv 8n^2-4n+1 \mod 64 $ using induction. I have seen the post which solves this problem using other methods, but I really need to be able to do it using induction.
Here is what I have so far:
Base step:
$5 \equiv 5 \mod 64$
Then, I assumed that $5^k \equiv 8k^2 -4k+1 \mod 64.$
I want to prove that $5^{k+1} \equiv 8(k+1)^2-4(k+1)+1 \mod 64$.
Note that $8(k+1)^2-4(k+1)+1=8k^2+12k+5$.
Hence,
$5^{k+1} \equiv 5^k *5 \mod 64
\equiv (8k^2-4k+1)*5 \mod 64 \equiv 40k^2 -20k+5 \mod 64.$
I am stuck here.
Any insight would be very useful!!
Thanks
Using binomial expansion,
$$5^n=(1+4)^n=1+\binom n1 4 + \binom n2 4^2 + \binom n3 \color{blue}{4^3} + \binom n4 \color{blue}{4^4} +\cdots + \binom nn \color{blue}{4^n}.$$
Since the binomial coefficients are integers and $4^3=64$, we have
$$5^n\equiv1+4n+8n(n-1)=8n^2-4n+1\bmod64.$$
A generalization
suggested by J. W. Tanner's answer.
If $0 &lt; j &lt; n$ then
$\begin{array}\\
(1+m)^n
&amp;=\sum_{k=0}^n \binom{n}{k}m^k\\
&amp;\equiv\sum_{k=0}^j \binom{n}{k}m^k \bmod m^{j+1}\\
\text{if }
&amp;j=2\\
(1+m)^n
&amp;\equiv\sum_{k=0}^2 \binom{n}{k}m^k \bmod m^{3}\\
&amp;\equiv 1+nm+\frac12n(n-1)m^2\bmod m^{3}\\
&amp;\equiv 1+n(m-\frac12m^2)+\frac12n^2m^2\bmod m^{3}\\
\text{if}
&amp;m=4\\
5^n
&amp;\equiv 1-4n+8n^2 \bmod 64\\
\end{array}
$