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

Question

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?

Answer 1

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.

Answer 2

$$(a+b)^5=a^5+b^5+5ab(a^3+b^3)+10a^2b^2(a+b)$$ $$(1+b)^5= 1+b^5+5b(1+b^3)+10b^2(1+b)=\color{red}{1+5bM}$$ $$\color{red}{2^4=1+5\cdot3}$$ $$2^{4\cdot5}=(1+5\cdot3)^5=1+5\cdot5\cdot3A=1+5^2M_1$$ $$2^{4\cdot5^2}=(1+5^2M_1)^5=1+5^3M_2$$ $$2^{4\cdot5^3}=(1+5^3M_2)^5=1+5^4M_3$$ the successive iteration makes it clear that $$2^{4\cdot5^{n-1}}=1+5^nM_{n-1}$$ ►EDITION.-It seemed to me that the color red was enough to associate the equalities above as correct. I will be more explicit in this edition but I leave my proof previous in sight to show that the proof is in general terms the same.

$(1+b)^5=1+b^5+5b(1+b^3+10b(1+b))$ and if $b=5c$ with $(5,c)=1$ then $$(1+b)^5=1+5^5c^5+5^2(c+5X)=1+5^2(c+5Y)=1+5^2M$$ where $(5,M)=1$ Here one has $2^4=1+15$ which implies $$2^{4\cdot5}=(1+15)^5=1+5^2M_1\iff2^{4\cdot5}\equiv1\pmod{5^2}$$ This shows that the order of $2$ modulo $5^2$ is $4\cdot5$ because if not then $2^k=1+5^2N$ where $k$ is an integer dividing $4\cdot5$ and less than $4\cdot5$ so $k=4$ or $k=5$ which is easily not possible.

Now continuing as above we clearly have for all $n$ $$2^{4\cdot5^{n-1}}=1+5^nM_{n-1}\iff2^{4\cdot5^{n-1}}\equiv1\pmod{5^n}$$ where $M_{n-1}$ is not divisible by $5$.

Proceeding now as in the case of the exponent $4\cdot5$, if $k$ were the order of $2$ module $5^n$ then $k$ should divide $4\cdot5^{n-1}$ so $k$ is equal to $4$ or $5^h$ or $4\cdot5^h$.

We know that for all $h\lt{n-1}$ we have $2^{4\cdot5^h}\equiv1\pmod{5^{h+1}}$ but $2^{4\cdot5^h}\not\equiv1\pmod{5^{n}}$. It follows that the only possibilities to be discarded are $k=4$ and $k=5^h$. Obviously $k\ne4$ and it remains the possibility $k=5^h$.

Suppose $2^{5^h}\equiv1\pmod{5^n}\Rightarrow2^{5^h}\equiv1\pmod5$ but $2^5\equiv2\pmod5$ so we have $2^{5^h}\equiv2\pmod5$, contradiction.

We are done: the order of $2$ modulo $5^n$ is $4\cdot5^{n-1}$

Answer 3

You don't really need induction to prove this formula, and the more general formula: $$\varphi(p^n)=p^{n-1}(p-1).$$ Indeed, represent the congruence classes $C$ $\bmod p^n$ by the integers from $0$ to $p^n-1$, and partition this set as follows: \begin{align}C&=\{0,1,\dots p-1\}\cup\{p,p+1,\dots,2p-1\}\cup\dots\cup\{(p-1)p,(p-1)p+1,\dots, p^2-1\} \\ &\phantom{{}={}}\cup\{p^2,p^2+1,\dots,(p+1)p-1\}\cup\dots\cup\{p^n-p,p^n-p+1,\dots,p^n-1\}. \end{align} Each set in this partition contains exactly $p-1$ elements coprime to $p$, since they all start with the consecutive multiples of $p$ which are less than $p^n$The number of these sets is the same as the number of multiples of $p$ between $0$ and $p^n-p$, which the same as the number of multiples of $p$ between $p$ and $p^n$, or, again, dividing by $p$, the number of integers between $1$ and $p^{n-1}$.

Answer 4

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&\equiv (g+p)^{p-1} \equiv g^{p-1} + (p-1)g^{p-2}p + \cdots + p^{p-1} \\ &\equiv g^{p-1} + (p-1)pg^{p-2}\mod{p^2} \\ &\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 \\ &= 1 + pbp^{n-1} + p^{n+1}(\ldots) \\ &\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.