# Proving $5^n \equiv 1 \pmod {2^r}$ when $n=2^{r-2}$

How can I prove that $5^n \equiv 1 (\bmod 2^r$) when $n=2^{r-2}$?

Actually what I am trying to prove is that the cyclic group generated by the residue class of $5 (\bmod 2^r)$ is of order $2^{r-2}$.

#### Solutions Collecting From Web of "Proving $5^n \equiv 1 \pmod {2^r}$ when $n=2^{r-2}$"

Hint: If $a=1\pmod{2b}$ then $a^2=1\pmod{4b}$.

(Proof: if $a=2bk+1$ then $a^2=4bk(bk+1)+1$. End of the proof.)

Use this for $a=5^n$, $n=2^{r-2}$ and $b=2^{r-1}$, to build a proof by induction on $r$, starting from the $r=2$ case $5^1=1\pmod{4}$.

We divide your original problem into two parts. The specific question you asked has nothing to do with $5$ and is answered for all odd $a$ in Part $1$. The fact that the order of $5$ is actually $2^{r-2}$ and not something smaller is proved in Part $2$.

Part $1$: Suppose that $a$ is odd, and $r \ge 3$. Then $a^{2^{r-2}}\equiv 1 \pmod{2^r}$.

Since $2^r$ does not have a primitive root, the order of $a$ modulo $2^r$ is less than $\varphi(2^r)$. But the order of $a$ divides $\varphi(2^r)$. Since $\varphi(2^r)=2^{r-1}$, it follows that the order of $a$ is a divisor of $2^{r-1}$ which is less than $2^{r-1}$. Thus the order of $a$ divides $2^{r-2}$. It follows that $a^{2^{r-2}}\equiv 1 \pmod{2^r}$.

Part $2$: We show that if $r\ge 3$, then $5^{2^{r-3}}\not\equiv 1 \pmod{2^r}$. This will show that the order of $5$ modulo $2^r$ is actually $2^{r-2}$, and not something smaller.

We show by induction that $5^{2^{r-3}}\equiv 1+2^{r-1} \pmod{2^r}$, and so in particular $5^{2^{r-3}}\not\equiv 1 \pmod{2^r}$.

It is easy to check that the result holds at $r=3$. Suppose now that $5^{2^{k-3}}\equiv 1+2^{k-1} \pmod{2^k}$. We show that $5^{2^{k-2}}\equiv 1+2^{k} \pmod{2^{k+1}}$.

By the induction assumption $5^{2^{k-3}}= 1+2^{k-1} +s2^k$ for some $s$. Square both sides, and simplify modulo $2^{k+1}$. We get that
$$5^{2^{k-2}}=(1+2^{k-1} +s2^k)^2 \equiv 1+2^k +2^{2k-2}\pmod{2^{k+1}}.$$
But $2^{2k-2}$ is divisible by $2^{k+1}$, since $k \ge 3$. The result follows.

Hint:
$$5^{2^{k+1}}-1=(5^{2^k}-1)(5^{2^k}+1)$$
The latter factor is always congruent to $2\pmod 4$. I recommend that you then prove a result giving the exact power of two that divides $5^{2^n}-1$ by induction on $n$. This gives you the order of the residue class of $5$ modulo any power of two.

Let a be an odd integer=2b+1(say),
$$a^2=4b^2+4b+1=8b(b+1)/2+1=8c+1$$(say) where $$c=b(b+1)/2$$ an integer (See also If $n$ is an odd natural number, then $8$ divides $n^{2}-1$)
$$a^4=(1+8c)^2=1+16c+64c^2=1+16d$$ for some integer $$d=c+4c^2$$
$$a^8=(1+16d)^2=1+32d+256d^2=1+32e$$
Using induction for n≥3,we get $$a^{2^{n-2}}≡1(mod 2^n).$$
See http://www.amazon.com/Introduction-Theory-Numbers-Ivan-Niven/dp/0471625469