If you find any mistakes, please make a comment! Thank you.

## Compute the order of 5 in the integers mod a power of 2

Solution to Abstract Algebra by Dummit & Foote 3rd edition Chapter 2.3 Exercise 2.3.22

Let $n$ be an integer with $n \geq 3$. Use the Binomial Theorem to show that $$(1+2^2)^{2^{n-2}} = 1 \pmod {2^n}$$ but that $$(1+2^2)^{2^{n-3}} \neq 1 \pmod {2^n}.$$ Deduce that 5 is an element of order $2^{n-2}$ in the group $(\mathbb{Z}/(2^n))^\times$.

Solution: We begin with some lemmas.

Lemma 1: Let $k$ be a positive integer and write $k = 2^m \cdot a$, where 2 does not divide $a$. Then $m+2 \leq 2k$.

Proof: If $k = 1$, we have $m=0$. Then $0 + 2 \leq 2 \cdot 1$, so the conclusion holds for $k=1$. If $k \geq 2$, we have $m < k$ by a lemma to a previous exercise; then $m+2 < k+k = 2k$. Thus the lemma holds for $k \geq 2$. $\square$

Lemma 2: Let $k$ be a positive integer with $k \geq 2$, and write $k = 2^m \cdot a$ where 2 does not divide $a$. Then $m+3 \leq 2k$.

Proof: If $k = 2$, we have $m = 1$. Then $1+3 \leq 2 \cdot 2$, so the conclusion holds. If $k \geq 3$, we have $m < k$ by a lemma to the previous exercise. Now $m+3 < k+k = 2k$, so the conclusion holds for all $k \geq 3$. $\square$

Now to the main result.

By the Binomial Theorem, we have $$(1+2^2)^{2^{n-2}} = \displaystyle\sum_{k=0}^{2^{n-2}} {2^{n-2} \choose k} \cdot 2^{2k}.$$Now by a lemma to the previous problem, if $2^{m_k}$ divides $k$, then $2^{n-m-2}$ divides $p^{n-2} \choose k$. Thus we have $$(1+2^2)^{2^{n-2}} = \displaystyle\sum_{k=0}^{2^{n-2}} 2^{n+2k-m_k-2} \cdot \beta_k,$$ for some integers $\beta_k$. Now by Lemma 1, $2k \geq m_k+2$ for all $k \geq 1$, so that $n+2k-m_k-2 \geq n$. Modulo $2^n$, all terms with $k \geq 1$ are zero, leaving only the $k=0$ term; thus we have $$(1+2^2)^{2^{n-2}} \equiv 1\ \mathsf{mod}\ 2^n.$$ We now consider $(1+2^2)^{2^{n-3}}$. Again by the Binomial Theorem, $$(1+2^2)^{2^{n-3}} = \displaystyle\sum_{k=0}^{2^{n-3}} {2^{n-3} \choose k} \cdot 2^{2k},$$ and using a lemma to the previous problem, if $2^{m_k}$ divides $k$ times, we have (for some integers $\beta_k$) $$(1+2^2)^{2^{n-3}} = \displaystyle\sum_{k=0}^{2^{n-3}} 2^{n+2k-m_k-3} \cdot \beta_k.$$ By Lemma 2, for all $k \geq 2$ we have $n+2k-m_k-3 \geq n$, so that, modulo $2^n$, these terms vanish. This leaves only the $k=0$ and $k=1$ terms. Thus, $$(1+2^2)^{2^{n-3}} = 1 + 2^{n-1},$$
which is not $1\pmod {2^n}$.

Thus, $|\bar 5|$ divides $2^{n-2}$ but does not divide $2^{n-3}$, so that we have $|\bar 5| = 2^{n-2}$ in $(\mathbb{Z}/(2^n))^\times$.