<s>[INST] Prove that if $a_{n+1} = a_n^2$, the last $n$ digits of $a_{n+1}$ are the same as the last $n$ digits of $a_n$. I have been working on this problem for a while. I know that I have to prove it using induction, but I'm unsure of the next step. The formula for the terms is: $a_{n+1} = 5^{2n}$ with $a_1 = 5$. The sequence is 5, 25, 625, etc. This is what I have thus far:
$a_{n+1} = a_n^2 = 5^{2n}$
$5^{2(n+1)} - 5^{2n} \equiv 0 \pmod {10^{n+1}}$
$5^{2n}5^2 - 5^{2n} \equiv 0 \pmod {10^{n+1}}$
$5^{2n}(24) \equiv 0 \pmod {10^{n+1}}$
Any hints? Thanks
 [/INST] The correct formula for $a_{n+1}$ in terms of $a_1$ is
$$
a_{n+1}=a_1^{2^n}\tag{1}
$$
You have $a_1=5$, so what you want to show is that
$$
5^{2^n}\equiv 5^{2^{n-1}}\pmod{10^n}\tag{2}
$$
which is equivalent to
$$
10^n\mid(5^{2^{n-1}}-1)5^{2^{n-1}}\tag{3}
$$
Now,
$$
\begin{align}
5^{2^{n-1}}-1
&=(5^{2^{n-2}}+1)(5^{2^{n-2}}-1)\\
&=(5^{2^{n-2}}+1)(5^{2^{n-3}}+1)(5^{2^{n-3}}-1)\\
&\hphantom{=\ }\vdots\\
&=\underbrace{(5^{2^{n-2}}+1)(5^{2^{n-3}}+1)(5^{2^{n-4}}+1)\dots(5^{2^0}+1)(5^{2^0}-1)}_{\text{$n$ terms, all of which are even, so divisible by $2^n$}}\tag{4}
\end{align}
$$
Therefore,
$$
2^n\mid5^{2^{n-1}}-1\tag{5}
$$
Furthermore, $2^{n-1}\ge n$ for $n\ge1$, so
$$
5^n\mid5^{2^{n-1}}\tag{6}
$$
$(5)$ and $(6)$ show that $(3)$ is true, which is equivalent to $(2)$.
</s>