# Order of $5$ in $\Bbb{Z}_{2^k}$

Is it true that the order of $5$ in $\Bbb Z_{2^k}$ is $2^{k-2}$? I was unable solve the congruence $5^n\equiv 1\pmod {2^{k}}$ nor see why $5^{2^{k-2}}\equiv 1\pmod {2^{k}}$. I’m not sure if this is the correct approach to this problem.

#### Solutions Collecting From Web of "Order of $5$ in $\Bbb{Z}_{2^k}$"

Your claim is true for $k\ge 3$. There is a solution in the link lhf provided, but here is another route: note that the order must be a power of $2$, and for any positive integer $m$ we have the factorization below: $$5^{2^m}-1=(5-1)(5+1)(5^2+1)\cdots(5^{2^{m-1}}+1)$$You want to find the smallest $m$ such that $2^n$ divides the left hand side. What can be said about the largest power of $2$ dividing the right hand side? (Hint: look at each term $\text{mod } 4$)

This technique is known as Lifting the Exponent.

Lemma 1: If $a$ is odd, $k\ge 3$, then $a^{2^{k-2}}\equiv 1\pmod{2^k}$.

Proof: Use induction. Base case: $a^2\equiv 1\pmod{8}$ for all odd $a$,

because if $a=2k+1$ for some $k\in\mathbb Z$, then $a^2-1=4k(k+1)$,

where $k(k+1)$ is a product of two consecutive integers, so $2\mid k(k+1)$.

If $a^{2^{m-2}}=2^mt+1$ for some $m\ge 3$, then

$a^{2^{m-1}}\equiv \left(2^mt+1\right)^2\equiv 2^{2m}t^2+2^{m+1}t+1\equiv 1\pmod{2^{m+1}}$.

Lemma 2: If $a\not\equiv 1\pmod{8}$, $k\ge 3$, then $a^{2^{k-3}}\not\equiv 1\pmod{2^k}$.

Proof: Use induction. Base case: $a\not\equiv 1\pmod{8}$.

If $a^{2^{m-3}}=2^mt+r$, $2\le r<2^m$ for some $m\ge 3$, then

$a^{2^{m-2}}\equiv \left(2^mt+r\right)^2\equiv 2^{2m}t^2+2^{m+1}tr+r^2\equiv r^2\pmod{2^{m+1}}$.

But $4\le r^2<2^{m+1}$, so $a^{2^{m-2}}\not\equiv 1\pmod{2^{m+1}}$.

Corollary: If $a$ is odd, $a\not\equiv 1\pmod{8}$, $k\ge 3$, then $\text{ord}_{2^k}(a)=2^{k-2}$.

In your case, it also turns out that $\text{ord}_{2^2}(5)=2^0$.

It is true and it can be proved by induction that $5^{2^{k-2}}\equiv 1\bmod {2^{k}}$ and $5^{2^{k-3}}\not\equiv 1\bmod {2^{k}}$.