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
 A: Assuming that the formula is actually $a_{n+1} = 5^{2^n}$ (which matches up with $a_{n+1} = a_n^2$ and $a_1 = 5$), then we have as follows:
$a_{n+1} - a_n = 5^{2^n} - 5^{2^{n-1}} = (5^{2^{n-1}})^2 - 5^{2^{n-1}} = 5^{2^{n-1}}(5^{2^{n-1}} - 1)$, and we want to show that this number is divisible by $10^n$.
Since $5$ and $2^n$ are coprime, we know from Euler's theorem that
$5^{2^{n-1}} \equiv 1 \pmod {2^n}$, since $\phi(2^n) = 2^{n-1}$. 
Thus, $(5^{2^{n-1}} - 1)$ is divisible by $2^n$.
For $n > 1$, we know that $2^{n-1} \geq n$, so $5^{2^{n-1}}$ is divisible by $5^n$.
Therefore, $5^{2^{n-1}}(5^{2^{n-1}} - 1)$ is divisible by both $5^n$ and $2^n$, and is therefore divisible by $10^n$ and we're done.
A: 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)$.
