Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 5 down vote accepted

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.
share|cite|improve this answer
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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.