# 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?

-
Because 5 is 1 mod 4? Anyway it hardly seems like a thing to loose sleep over. – David Loeffler Aug 29 '12 at 19:23
@DavidLoeffler As I said in my comment to Jyrki's answer, this was motivated by being questioned why I don't use 3 instead of 5 and not having a good answer. (I was treating 4 separately, anyway, so my proof worked verbatim for 3.) – Phira Aug 29 '12 at 20:39

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.
-
Thanks a lot! I will have to decide for myself if these advantages compensate the disadvantage that students are left with the vague impression that 3 won't work. – Phira Aug 29 '12 at 20:38
@Phira: Yeah, the most "compelling" difference probably is the modulo 4 case. The formula $\mathbb{Z}_{2^n}^*=\langle 5\rangle \times\langle -1\rangle$ works for all power of $2$. Replace $5$ with $3$ and you need to exclude $4$. – Jyrki Lahtonen Aug 30 '12 at 7:12

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.

-