Euler's totient problem: Prove that the order of $2 \bmod 5^n$ is always equal to $4\cdot 5^{n-1}$ Prove that the order of $2 \bmod 5^n$ is always equal to $4\cdot 5^{n-1}$.


I know that the order must divide $4\cdot 5^{n-1}$ because of Euler's totient, but how do I move forward from here?
There is probably an easier way of proving this, particularly since you are interested in the special case $p=5$, but here is a proof for the general case.

Suppose $p$ is an odd prime and $g$ a primitive root modulo $p$. We first show that either $g$ or $g+p$ is a primitive root modulo $p^2$. (Note that this can be proved more easily using Hensel's Lemma.)

We have for $n\ge 2$ that
\begin{equation*}
  g^{\mathrm{ord}_{p^n}g}\equiv 1\mod{p^n}\quad\Rightarrow\quad
  g^{\mathrm{ord}_{p^n}g}\equiv 1\mod{p} \quad\Rightarrow\quad
  p-1 = \phi(p)\mid \mathrm{ord}_{p^n}g.
\end{equation*}
But also $\mathrm{ord}_{p^n}g\mid \phi(p^n) = p^{n-1}(p-1)$, so that $\mathrm{ord}_{p^n}g = p^k(p-1)$ for some $0\le k\ne n-1$. For $n=2$, if $k=1$ then $g$ is primitive modulo $p^2$. Otherwise, $\mathrm{ord}_{p^2}(g+p) = p-1$ or $p(p-1)$. In the former case, we get
\begin{align*}
  1&amp;\equiv (g+p)^{p-1} \equiv g^{p-1} + (p-1)g^{p-2}p + \cdots + p^{p-1} \\
  &amp;\equiv g^{p-1} + (p-1)pg^{p-2}\mod{p^2} \\
  &amp;\equiv g^{p-2}(g-p)\mod{p^2},
\end{align*}
but this is impossible since $p\nmid g$. Thus $g+p$ is primitive modulo $p^2$. (Note that in your case, $2$ is also primitive modulo $25$, so we can take $g=2$ in what follows.)

Now let $g$ be a primitive root modulo $p^2$ and modulo $p$. Claim $g$ is a primitive root modulo $p^n$ for any positive integer $n$. From before, $\mathrm{ord}_{p^n}g = p^k(p-1)$; we wish to show that $k=n-1$. It suffices to show that $g^{p^{n-2}(p-1)}\not\equiv 1\mod{p^n}$. Using induction on $n$, the base case $n=2$ is our assumption. Assume that the statement holds for $n$. Then from the inductive assumption, we have $g^{\phi(p^{n-1})}\not\equiv 1\mod{p^n}$, while Fermat's little theorem gives $g^{\phi(p^{n-1})}\not\equiv 1\mod{p^{n-1}}$, so that $g^{\phi(p^{n-1})}=1+bp^{n-1}$ with $p\nmid b$. Thus (with $n\ge 2$)
\begin{align*}
  g^{p^{n-1}(p-1)} = (1+bp^{n-1})^p \\
  &amp;= 1 + pbp^{n-1} + p^{n+1}(\ldots) \\
  &amp;\equiv 1+bp^n\mod{p^{n+1}}.
\end{align*}
Since $p\nmid b$, the order of $g$ modulo $p^{n+1}$ must be $p^n(p-1)$ and we are done.
Prove by induction on $n$. Can be shown for $n=1$ and $2$ by computation.  

Now assume true for $n=k\ge2$.

As you indicated, noting Euler's totient function, the order of $2$ modulo $5^{k+1}$ divides $4\times5^k$.  

To show it is not smaller than $4\times5^k$,

it suffices to show that $2^{2\times5^k}-1$ and $2^{4\times5^{k-1}}-1$ are not divisible by $5^{k+1}$.

But if $5^{k+1}$ divides $2^{2\times5^k}-1$ then certainly $5^k$ divides it, and given that $5^k$ divides $2^{4\times5^{k-1}}-1$, 

it would follow that $5^k$ divides $2^{2\times5^{k-1}}-1,$ contradicting the inductive hypothesis.

Likewise, $5^{k+1}|2^{4\times5^{k-1}}-1=(2^{4\times5^{k-2}}-1)(2^{4\times4\times5^{k-1}}+2^{4\times4\times5^{k-1}}+2^{4\times3\times5^{k-1}}+2^{4\times2\times5^{k-1}}+1)$

$\implies5^k|2^{4\times5^{k-2}}-1,$ since $5|(2^{4\times4\times5^{k-1}}+2^{4\times4\times5^{k-1}}+2^{4\times3\times5^{k-1}}+2^{4\times2\times5^{k-1}}+1);$ 

again, we have a contradiction to the inductive hypothesis.