Exercise 2.3.22 (Order of $\overline{5}$ in the group $(\mathbb{Z}/2^n \mathbb{Z})^\times$)

Proof. We show by induction on $k\ge 3$ the property $𝒫(k)$, where

• If $k=3$, then $5^{p^{k-3}}=5$, and $1+2^{k-1}=5$, so $𝒫(3)$ is true.

• Suppose that $𝒫(k)$ is true for some $k\ge 3$, so that

  $$5^{2^{k-3}}=1+2^{k-1}+\lambda 2^k,$$

  for some integer $\lambda$. Then

  $$\begin{array}{llll}\hfill 5^{2^{k-2}}& ={\left(5^{2^{k-3}}\right)}^2& \hfill & \\ \hfill & ={(1+2^{k-1}(1+2\lambda ))}^2& \hfill & \\ \hfill & =1+2^k(1+2\lambda )+2^{2k-2}{(1+2\lambda )}^2& \hfill & \\ \hfill & =1+2^k+2^{k+1}\lambda +2^{2k-2}{(1+2\lambda )}^2.& \hfill & \end{array}$$

  Since $k\ge 3$, then $2k-2\ge k+1$, therefore $2^{2k-2}\equiv 0(\mathit{mod}{2}^{k+1})$. This gives

  $$5^{2^{k-2}}\equiv 1+2^k(\mathit{mod}{2}^{k+1}),$$

  so $𝒫(k+1)$ is true.

• The induction is done, which proves that

  $$\forall <!--\; FUNCTION\; APPLICATION\; -->k\in ,k\ge 3\Rightarrow 5^{2^{k-3}}\equiv 1+2^{k-1}(\mathit{mod}{2}^k).$$

  In particular, if $n\ge 3$, $5^{2^{n-2}}\equiv 1+2^n(\mathit{mod}{2}^{n+1})$, and since $2^n\mid 2^{n+1}$,

  $$\begin{array}{llll}\hfill 5^{2^{n-2}}& \equiv 1(\mathit{mod}{2}^n),& \hfill & \\ \hfill 5^{2^{n-3}}& \equiv 1+2^{n-1}\not\equiv 1(\mathit{mod}{2}^n).& \hfill & \end{array}$$

  Therefore ${\bar{5}}^{2^{n-2}}=\bar{1}$ and ${\bar{5}}^{2^{n-3}}\ne 1$ in ${(\mathbb{Z}∕2^n\mathbb{Z})}^{\text{×}}$. If $d$ is the order of $\bar{5}$ in this group, then $d\mid 2^{n-2}$ and $d\nmid 2^{n-3}$, hence $d=2^{n-2}$.

  In conclusion, $\bar{5}$ is an element of order $2^{n-2}$ in the multiplicative group ${(\mathbb{Z}∕2^n\mathbb{Z})}^{\text{×}}$.