Generators of the multiplicative group modulo $2^k$

In most books and lecture notes that explicitly give generators of the multiplicative group of the odd integers modulo $2^k$, the set $\{-1, 5\}$ is offered.

However, the number 5 can be replaced by 3 which seems more logical for a standard choice. The proof I know do not suffer from these change.

Is there a particular reason for this traditional choice of generator?

Solution 1:

I agree with David Loeffler that there is very little behind this. The few reasons for preferring five over three that I can think of are (all related):

1. The order of $5$ modulo $2^n, n\ge2,$ is always $2^{n-2}$, but with $3$ we must make an exception, when $n=2$. So using five allows a slightly more uniform description.
2. The coset of $5$ generates the kernel of the natural projection $\mathbb{Z}_{2^n}^*\rightarrow \mathbb{Z}_4^*, n\ge2.$
3. We have the well known realization of $\mathbb{Z}_{2^n}^*$ as the Galois group $Gal(\mathbb{Q}(\zeta)/\mathbb{Q})$, where $\zeta=e^{2\pi i/2^n}$, and the unit $u$ corresponds to the automorphism $\sigma_u:\zeta\mapsto\zeta^u$. As $5\equiv 1\pmod 4$, the fourth root of unity is fixed under $\sigma_5$, and it easily follows that the field of invariants is $\mathrm{Inv}(\langle\sigma_5\rangle)=\mathbb{Q}(i)$, which is, perhaps, the quadratic subfield that first comes to mind. OTOH (assuming that $n\ge3$) we have $\mathrm{Inv}(\langle\sigma_3\rangle)=\mathbb{Q}(\sqrt{-2}),$ which is a bit less obvious.

Solution 2:

I've seen this proved by proving that $5^{2^{k-3}} \equiv 1 + 2^{k-1} \not\equiv 1\bmod 2^k$, for $k\ge 3$, using induction. (See for instance Elementary Number Theory by Bolker.)

On the other hand, $3^{2^{k-3}} \equiv 1 + 2^{k-1} \bmod 2^k$, for $k\ge 4$ but not for $k=3$, even though it is still true that $3^{2^{k-3}} \not\equiv 1\bmod 2^k$ for $k=3$.

So, using $5$ allows a slightly shorter proof.