# The Units Mod p are Cyclic

First, let me apologize for interupting Ben’s series of followups with some mathematics. Today, I want to explain a proof of the fact that the units modulo p are cyclic that I stumbled accross a couple years ago. It’s basically the same as Gauss’s counting argument, except without counting anything. It’s needlessly complicated, but still kind of cute.

Here’s the basic outline: since the cyclotomic polynomials are defined over the integers you can leverage your knowledge about the roots of unity in the complex numbers (which is obviously a cyclic group) into a proof that the roots of unity in the integers modulo p is also cyclic.

First a little background. Define the dth cyclotomic polynomial $\Phi_d(x) = \prod_{\zeta} (x-\zeta)$ where $\zeta$ ranges over all primitive dth roots of unity in the complex numbers. Clearly $\prod_{d \mid n} \Phi_d(x) = x^n-1$ (since every root of unity is a primitive root of unity for some $d \mid n$). By Mobius inversion, $\Phi_n(x) = \prod_{d \mid n} (x^d-1)^{\mu(n/d)}$. This means that $\Phi_n(x)$ is a ratio of two monic integer polynomials, but also it is a polynomial with complex coefficients. This implies that it is a polynomial with integer coefficients! To see that, notice that when you do the division algorithm over the complex numbers to two integer monic polynomials you never leave the integers. This fact will allow us to turn our knowledge about roots of unity in the complex numbers (which are cyclic for obvious geometric reasons) into knowledge about roots of unity in any ring.

Now let p be a prime number and let n=p-1 be the size of the unit group. A generator of the unit group is a root of $x^n-1$ which is not a root of $x^d-1$ for d any proper divisor of n. Equivalently a generator is a root of $\Phi_n(x)$ which is not also a root of $\Phi_d(x)$ for d a proper divisor of n.

By Fermat’s Little Theorem, every unit modulo p is an nth root of unity. Since $x^n-1 = \prod_{d \mid n} \Phi_d(x)$ in the integers, this identity is also true modulo p. But the left side has n distinct roots. So the right side also must have n distinct roots. Since it is a polynomial of degree n over a field, this means each of its factors must split completely. Hence $\Phi_n(x)$ has exactly $\deg \Phi_n(x)$ roots, and none of these roots are also roots of $\Phi_d(x)$ for d a proper divisor of n. Thus all we need to do is prove that $\Phi_n(x)$ is nonconstant, which again is obvious because of the geometric structure of the complex numbers.

(Exercise: use this same technique to show that a finite subgroup of the multiplicative group of a field is cyclic. Hint: the integers are the universal ring.)

To turn this into Gauss’s counting argument, just take degrees everywhere. That is Gauss’s argument shows that the number of elements of degree d is $\varphi(d)$, while this argument just shows that the number of elements of degree d in the units modulo p is the same as the number of elements of degree d in the complex plane (which happens to be $\varphi(d)$).

## 16 thoughts on “The Units Mod p are Cyclic”

1. First, let me apologize for interupting Ben’s series of followups with some mathematics.

Oooh, burn. Whatever, I still write more math posts than you do. Not to mention that I wrote a math post a couple weeks, which, as far as I can tell, nobody read.

2. This post is interesting for me, because I was just teaching that the units in a finite field are cyclic, and I used the standard overkill method of first classifying finite abelian groups. Your point is that you can replace that classification by Mobius inversion (which however is still non-trivial.)

But I think that complex numbers are not needed in the argument, although I suppose that it’s valid to use them. You’re also saying this: (1) In any field, the equation xd = 1 has at most d solutions. (2) In a finite field with q elements, xq-1 = 1 has q-1 distinct solutions, by Lagrange’s theorem for finite groups; in particular, it is a multiplicity-free polynomial. (3) If field xa = 1 has a distinct solutions in some field, then xd = 1 has d distinct solutions for any d|a, because xd-1 divides xa-1. (4) By Mobius inversion, you can conclude that xq-1 = 1 has exactly φ(q-1) solutions which are not lower-order roots of unity; the multiplicative group is therefore cyclic.

So yes, Mobius inversion is a reasonable alternative to the classification of finite abelian groups in this result.

Note also that the result, proved in either style, has an interesting generalization which is not usually mentioned: If an integral domain R has only finitely many roots of unity, then its roots of unity form a cyclic group. A theorem can become confusing if it no longer seems newsworthy, in which case it helps to find a creative generalization in which the same argument applies. This generalization to integral domains serves that purpose.

Okay, here is another generalization: If R is any integral domain, then its roots of unity are an ind-cyclic group. I.e., they are isomorphic to the additive group A/nZ, where Z is the integers, n is an integer, and A is the integers localized at some set of primes.

3. Blech, WordPress killed all of my superscripts. Can we not have a preview feature?

4. anon says:

Heh, here’s a very slightly different “softer” proof of the same thing I came up with while preparing for quals — it still goes by reduction to universal rings and C, but doesn’t use Mobius inversion.

Goal: For a field K, a finite subgroup G of K* is cyclic.
Proof: As G is torsion, we reduce to the case of mu_n(K) for some n. If K has characteristic 0, we reduce to C (Lefschetz) and then we know the result. If K has characteristic p, we may assume n is prime to p. As mu_n is algebraic, we may take K = F_q for some q. Since n is prime to p, mu_n is a finite etale group scheme over W(F_q) (or any other complete char 0 dvr with residue field F_q), so mu_n(F_q) = mu_n(W(F_q)) = mu_n(W(F_q)[1/p]) (the first equality by finite etaleness of mu_n, the second by properness). We’re now in the char 0 case, which we know.

5. Pete L. Clark says:

I like the idea of working with cyclotomic polynomials themselves rather than with their degree relations, so I think that Noah’s proof is interesting. I agree with him that it is more complicated than necessary, though.

In order to prove the most general result in question — that any finite subgroup of the multiplicative group of a field is cyclic (Greg Kuperberg’s observations about integral domains are quick corollaries of this) — one needs only to establish the following

Theorem (Cyclicity Criterion): Let G be a finite group of order n. If
for all d | n, there are at most d elements x in G satisfying x^d = e, then G is cyclic.

(One then applies the fact that the degree d polynomial t^d – 1
can’t have more than d roots in any field.)

To establish the theorem one needs only Lagrange’s theorem together with the identity

sum_{d | n} phi(d) = n.

In fact, if one only wants the result for commutative groups, then the
special case of Lagrange’s theorem that the order of an element divides the order of the group can be established using one of the standard proofs of Fermat’s little theorem (the one which uses the fact that multiplication by g in G permutes the elements of G).

As for the identity, it is easily established in several different ways (perhaps most directly by counting the number of elements of order d in a cyclic group of order n), and is a standard part of most elementary number theory / algebra curricula anyway.

These ideas are written up in more detail at

http://www.math.uga.edu/~pete/4400algebra2point5.pdf

6. Anonymous says:

I think Gauss’s proof is not the one you have in mind (which is also classical). Here is what I recall is Gauss’s proof. Factor $n=p-1=q_1^{a_1}\ldots$ (I hope the TeX works). The equation $x^{n/q_i} = 1$
has at most $n/q_i$ roots so there exists $b_i$ with $b_i^{n/q_i} \ne 1$. Then
$b_i^{n/q_i^{a_i}}$ has order $q_i^{a_i}$ and the product of these guys has order $n$.

7. Anonymous says:

Correction. Gauss actually gives both proofs. The one I sketched is in Art. 55 of Disquitiones and the alluded above is in the previous article. Check it out on google books:

8. As far as this particular result is concerned (a finite subgroup of the multiplicative group of a field is cyclic, where fields are assumed commutative), one can use abelian groups without needing the full classification of finite abelian groups, by an ad-hoc argument. What is needed is to show that a finite abelian group G in which the equations x^d=1, for d positive integer, always have at most d solutions, is cyclic. This can be done directly (it’s particularly clear after splitting G in product of p-groups, but this step is not even necessary).

Incidentally, this basic fact about x^d-1 is present in all the arguments above (and seems to be the essential point) except for the one in Comment 4. Since the latter has a number of black boxes (Lefschetz principle, Witt vectors, finite étale group schemes), I wonder if there isn’t some circularity hidden…

9. AnotherAnon says:

Anon#4: I used the same proof in a undergrad Galois theory course last year. It was the last lecture–in it we defined the p-adics etc etc. It’s a great way to end such a course— it explains a choice of generator for the cyclic group in terms of the choice of an embedding of Q_p into C, ie exactly the torsor the Galois group acts on.

10. Yes, the ad hoc argument Emmanuel mentions is given on page 2 of Weil’s Basic Number Theory: let a be an element of maximal order n (in a finite abelian group G with that property). Let b be any other element, with order d, and suppose (for a contradiction) that d does not divide n. There is a prime power q such that q divides d but not n. Then one checks that the order of ab^{d/q} is the lcm of n and q, contradicting maximality of n.

So d|n. The equation x^d = 1 has solutions x = a^{n/d}, a^{2n/d}, …,: d of them, all distinct. Since there are at most d solutions, the element b must be one of them. So a generates.

11. Scott Carnahan says:

On a slightly related note, I remember a Berkeley prelim problem from sometime late in the last century that was roughly: show that the group of units of a ring does not have order 5.

12. Am I alone in thinking that prelim problem looks a little bit nasty? Or is there some easy argument that one can reasonably be expected to produce under time pressure and mental duress?

[Are Berkeley prelims oral? If they are, do the examiners generally throw out little hints if the examinee gets stuck?]

13. The Berkeley prelims are written. You get 6 hours and you only need to solve half of the problems, so it’s certainly ok if some of them stump you. We have oral quals, but they’re later on in the program.

This one didn’t look too bad to me (it’s exactly the sort of excercise I like). Though when I first thought about it I mistakenly only did the case where R was a domain. If I’ve done the argument correctly the same proof should work for any odd prime not of the form $2^n-1$. Here’s a ROT13ed clue for anyone who wants it: Gnxr pnfrf onfrq ba gur punenprevfgvp bs gur evat.

14. Well, I did register before the observation that the punenpgrevfgvp bs gur evat is gmb, but now that I’ve thought about it again, I see an argument alternative to my original one which makes it seem a lot easier to me now. That is, my original argument was based on the structure of the group ring Z[G] where G is cyclic of order 5, but I see that line of thinking is much harder than need be (and I think your generalization is right). Thanks.

15. I hadn’t seen this type of problem before. I think it’s nice, and I’m tempted to use it at some point, either in an algebra or a number theory course. It’s the sort of problem that would be much easier if you asked it at the appropriate point in a course (say after having covered the arithmetic of finite fields…).

This would indeed be a challenging problem for our algebra qualifying exam at UGA (typically we ask our students to solve all of the problems on the exam), but I do think it’s enlightening to know whether a student can solve it or not, because it doesn’t require any very specialized knowledge, but would be hopeless for anyone without a pretty solid understanding of groups and rings.

I wonder idly: do the same considerations completely answer the question of which finite commutative groups can be the full unit group of a commutative ring? (Up to existence of Mersenne primes.)