## Collecting proofs that finite multiplicative subgroups of fields are cyclic.

I teach elementary number theory and discrete mathematics to students who come with no abstract algebra. I have found proving the key theorem that finite multiplicative subgroups of fields are cyclic a pedagogical speedbump. For example, Serre's proof in A Course in Arithmetic runs a full page, requires introducing Euler's $\phi$-function, and depends on a counting argument that might seem to beginners too clever or magical for a cornerstone result.

I'd like to have a collection of proofs of this fact, to compare their advantages, to match their viewpoints to my various audiences, to contrast for my students, etc.

To get the ball rolling, here's the shortest argument I can think of (and if it's in the literature somewhere I'd love a reference).

Induction on the order of the subgroup. So suppose multiplicative subgroup $G$ of field $F$ has order $n$. If $n=p^k$ with $p$ prime and $G$ isn't cyclic, all $p^k$ elements of $G$ satisfy $x^{p^{k-1}}-1=0$, impossible.
If $n=ab$, $gcd(a,b)=1$, then $(\cdot)^a:G\rightarrow G$ has a kernel $A$ of size at most $a$ and a range $B$ of size at most $b$ (since the $y\in B$ satisfy $y^b=1$), so $|A|=a$, $|B|=b$, and a product $xy$ of cyclic generators $x,y$ for $A,B$ respectively generates $G$.

If you know published proofs distinctly different from either of these, please cite a source. No need to spell out the details, but please mention a key feature to help avoid duplicates. If you have your own favorite approach, please share it.

-
It looks like your short argument uses a nontrivial assertion about the exponent of a non-cyclic abelian $p$-group, and another assertion about the number of roots of a polynomial over a field. In particular, I don't see why this argument is substantially simpler than the corresponding fact for the case of $n$ with more than one prime divisor (which would allow you to eliminate the last sentence). – S. Carnahan Feb 8 2011 at 8:59
Well, it depends on what you want to use. The argument you give can be shortened somewhat by using that the order of any element in a finite abelian group divides the maximal order (and then noting that because of this, if m is the maximal order, then all elements in the subgroup are roots of a polynomial of degree m) – Tobias Kildetoft Feb 8 2011 at 9:03
One more comment: don't you want to introduce Euler's $\varphi$ function in a number theory course? As a number theorist, I would defend introducing it even in a pure algebra course, but in a number theory course it seems almost mandatory. – Pete L. Clark Feb 8 2011 at 10:02
@Pete I will teach Euler's $\phi$ and circle back to this theorem. But here's my pedagogical axe (and MO might not be the right place for this discussion...but where?) My students lack mathematical maturity and thus don't relish proofs that depend on extrinsic ideas. I aim to get them used to all that, but using examples where extrinsic ideas are essential. But with this proof, I think $\phi$ enters as a mere bookkeeping device. The mysterious stranger will seem like the protagonist in a short mysterious tale, which misleads beginners. – David Feldman Feb 8 2011 at 23:38
@Pete, cont. My pedagogical principle with students who lack mathematical maturity aims at postponing the "I never could have thought of that in a million years moments," in order to foster a sense that proofs of cornerstone theorems really would emerge given sufficient time and thought. – David Feldman Feb 8 2011 at 23:38
show 1 more comment

Let $G$ be a finite subgroup of $F^{\ast}$ of order $n$. Then all the elements of $G$ satisfy $x^n = 1$ in $F$. Since polynomials of degree $n$ over a field have at most $n$ roots, it follows that the roots of $x^n = 1$ in $F$ are precisely the elements of $G$.

The intuitive content of Serre's argument is as follows: if no element of $G$ has order $n$, then they all have to have order less than $n$, so they satisfy various smaller polynomials $x^d = 1$ for $d | n$, and what the counting argument is trying to show is that there isn't enough "room" in these polynomials for all of these roots. I think this is quite intuitive, and it is completely clear for $n$ a prime power, but you want to avoid it, so:

Over $\mathbb{C}$, the roots of $x^n = 1$ are precisely the $n^{th}$ roots of unity. It is natural to organize these by their order, so let $\Phi_d(x) = \prod_{\zeta \text{ has order exactly } d} (x - \zeta)$. The result that Serre is trying to avoid with his counting argument is that $\Phi_d(x)$ has integer coefficients, so the factorization

$$x^n - 1 = \prod_{d | n} \Phi_d(x)$$

makes sense over an arbitrary field. If you can show this, the rest of the proof is trivial: since $x^n = 1$ splits over $F$, it follows that $\Phi_n(g) = 0$ for some $g \in G$, and such an element must have order $n$ and therefore be a generator.

If your students really have no algebra background I think you should consider stating this without proof. It is easy to give examples and hopefully you can give enough to convince them.

The shortest way I can think of to prove that $\Phi_n(x)$ has integer coefficients is by induction and the identity $\gcd(x^n - 1, x^m - 1) = x^{\gcd(n,m)} - 1$, which again 1) is intuitive over $\mathbb{C}$ but 2) makes sense over an arbitrary field. But this is a bit of a detour and precisely why Serre did something trickier. However, I think the larger lesson that "algebraic things that are intuitive over $\mathbb{C}$ are worth generalizing" is worth learning.

-
Initially, I didn't see why it was necessary to mention the complex numbers, since the statement about the $n^{th}$ roots of unity seemed a little tautological. Now I think you may be suggesting that in the complex case there is both a geometric way to visualize the fact that finite torsion subgroups of $\mathbb{C}^\times$ are cyclic, and an explicit formula for elements of order exactly $n$. – S. Carnahan Feb 8 2011 at 10:31
We need to find ONE field extension of $\mathbb Q$ which contains a primitive $n$-th root of unity. How do you do this without complex numbers? This is exactly the reason why I dislike Quiaochu's proof: it's geometric. – darij grinberg Feb 8 2011 at 10:45
@Scott: more or less. That comment about complex numbers is entirely by way of motivation, e.g. "let's motivate this factorization and then prove it exists over Z." I think it is okay to emphasize motivation over rigor in a first course like the one described, and students should be made thoroughly aware of the complex case if they aren't anyway. – Qiaochu Yuan Feb 8 2011 at 10:56
Without $\mathbb C$, how do you know that $\Phi_n\neq 1$? – darij grinberg Feb 8 2011 at 17:37
@darij: $\Phi_n$ is uniquely defined by Mobius inversion, if you prefer. – Qiaochu Yuan Feb 8 2011 at 17:49

I actually think it will not be so easy to say when two proofs of this result will be "distinctly different": rather I expect most or all will have common features, including using at least a little bit of group theory.

For instance, the proof I wrote up for my elementary(ish) number theory course is Theorem 9 in these notes. The notes themselves are on finite commutative groups, and Theorem 9 is on page 3, in the section on "cyclic groups". Prior to the statement and proof, a little over a page is spent developing the basic properties of cyclic groups, including a statement involving the Euler $\varphi$-function. The proof of the result itself -- which, note, is a criterion for an a priori noncommutative finite group to be cyclic -- occupies $11$ lines. (Added: sorry, false advertising -- add two more lines to get from Theorem 9 to Corollary 10, which is the statement that any finite subgroup of the multiplicative group of a field is cyclic.) I certainly think it is more or less the proof that any research mathematician is expecting to find.

Let me mention though that I had originally included this argument as an application of the Mobius Inversion Formula. After having looked back at what I'd done, I decided that although the argument was reminiscent of an inversion / inclusion-exclusion counting argument, it only made it more complicated to phrase it in that way.

-
After checking back in Serre's Course of Arithmetic, it seems that the proof in the notes I linked to is all but identical to the one in Serre's book (what a coincidence!). So I guess my answer amounts to a defense of his proof: it seems perfectly lovely to me. (Interestingly, a semester of abstract algebra was a prerequisite for my course, but that one semester does not cover groups. So my solution was to write up some notes on the basic group theory that would be needed in my course.) – Pete L. Clark Feb 8 2011 at 9:55
This is the proof from Gauss's Disquisitiones. – Franz Lemmermeyer Feb 8 2011 at 15:26

Let $n = |G|$ and let $m$ be the l.c.m. of the orders of the cyclic factors of $G$. Then $x^m = 1$ for all $x \in G$; since we are in a field this equation has at most $m$ roots, which shows that $m \geq n$. It follows that $m = n$ and $G$ is cyclic.

Of course here one uses the classification of finite abelian groups as product of cyclic groups, which you may want to avoid.

-
@Andrea: in my opinion, you are using a much harder result to prove a much easier result. It doesn't make much sense. If you read Serre's book carefully, he makes a point of never using the structure theorem for finite abelian groups (and he makes it all the way to Dirichlet's theorem in this way). I have some remarks on this in Section 4.4 of the notes linked to in my answer. (And then in Section 5 I prove the structure theorem, so you can see how much harder it is!) – Pete L. Clark Feb 8 2011 at 10:05
I think you can get away with using a weaker result that is independently useful: namely, let n be the lcm of the orders of all elements of G and then prove that if an abelian group has elements of orders n and m then it has an element of order lcm(n, m). I don't remember how hard this is to prove from first principles, though. – Qiaochu Yuan Feb 8 2011 at 11:23
@Qiaochu Yuan: It's relatively easy. First prove that $ord(xy)=ord(x)ord(y)$ if $gcd(ord(x),ord(y))=1$. Then prove that for every divisor of $ord(x)$ there is a power of $x$ with exactly that order. Then use the characterization of the lcm in terms of prime decomposition to show that there are exponents $k,m$ such that $ord(x^k y^m)=lcm(ord(x),ord(y))$. – Johannes Hahn Feb 8 2011 at 11:31
@Pete: Yes, I'm aware that classification of finite abelian groups may be a cannonball here. On the other hand, in the introductory algebra course in Italy one usually encounters groups before more complicated structures like fields (at least, it used to be like that) so one may have the result at hand anyway. In any case the question was about collecting proofs of this results, so I thought it may be worth to add this one. :-) – Andrea Ferretti Feb 8 2011 at 12:41
@Johannes: nice. I think that entire argument is simpler than any of the proofs that have been presented so far, but maybe I am missing some subtlety. – Qiaochu Yuan Feb 8 2011 at 17:51

I know less than you know in the topic since you are a teacher now.
However, I want to mention two sources you can find the proof which use little prerequisites of algebra.
First of all, the classic Basic Nuber Theory by Andre Weil contains a proof in the first section of the first chapter which uses a great method.
As for the second, the Chinese mathematician Hua, Lo-keng ( in Chinese 華羅庚 ) has published a book entitled Introduction to number theory, which has a proof that uses only elementary terminologies, and I hope it is exactly what you need.
By the way, the first approach is the same as that mentioned by @QiaoChu Yuan in some sense, and the second is mostly elementary.
P.S. I hope it is acceptable here using Chinese, thanks.

-
 Weil's proof in Basic Number Theory is indeed short and sweet. In his Number Theory for Beginners (a gem of a book!) the proof is the standard one, similar to Serre's. – lhf Feb 8 2011 at 12:38 If it's so short and sweet, how about sharing it with us? Unfortunately, Weil isn't on my bookshelf. – Kevin O'Bryant Feb 8 2011 at 22:50 @Kevin: Amazon's Look Inside allows you to read page 2, which is where the proof is. See First Pages. – lhf Feb 22 2011 at 12:33 @Kevin: I think I can give you a brief guide to the proof as follows: First of all, we all know that a pure polynomial can have no more roots than the degree. Then suppose a is an element in the group which has the maximal order, we can show that if an element of the group is not of the order dividing that of a, then there exists an element of order greater than that of a, hence every element is a root of $x^{n}=1$ where n is the order of a, and hence by what we have shown, every element is a power of a, which is what we want to prove. My post is a supplement, please forgive any flaw. – awllower Feb 24 2011 at 9:40 I just noticed that the book is available in amazon, if you are lazy to view that book in person, then this post serves as a brief guide, which does not catch any spirits of the original proof. – awllower Feb 24 2011 at 9:42

I once collected six proofs of this theorem, for the field Z/p, and they can be found at http://www.math.uconn.edu/~kconrad/blurbs/grouptheory/cyclicFp.pdf. While Z/p is not the general finite field, since the intent of this MO question is to use proofs in a course to undergraduates without much background, surely Z/p is the only finite field that matters.

-
 Well, this certainly seems like the best possible answer to this question! – Pete L. Clark Feb 8 2011 at 17:31 Pete--Surprisingly, the proof that the proposer and I give doesn't appear to be one of Keith's six. – paul Monsky Feb 8 2011 at 17:44 Paul: it's not that surprising (to me) since I basically brought together the proofs I was able to find in books. Now I'll have to include the proof you describe, someday... – KConrad Feb 9 2011 at 1:30

Let n be the number of elements of F*, p be a prime dividing n, q be the largest power of p dividing n; let r=q/p. Look at the map x-->x^(n/q), F*-->F*. The kernel has order at most n/q, so the image has order at least q, and there are at least q solutions of x^q=1. Since there are at most r solutions of x^r=1, there is an element of exact order q; multiplying these elements together for the various p dividing n gives a generator.

(I've used this no doubt well-known argument successfully in undergrad courses).

Edit: For the final step, let u be the product. Then u^(n/p)=a^(n/p) where a has exact order q. So u^(n/p) is not 1 for all p, and u has exact order n, and is a generator. Looking again at the question, I realize that this is essentially the same as the proposer's short solution, though I've restricted my attention unnecessarily to finite fields. But it combines Lagrange's theorem with the theorem that x^m=1 has at most m solutions in F* in a very simple way.

-

I don't know how helpful this is for anybody, especially students, but for finite subgroups $G$ of $\mathbb C^*$ you can first observe that every element has modulus $1$, so is on the unit circle and has rational argument, and then choose the element $z$ of least non-zero argument. Then, given $y\in G$, rotate clockwise by dividing by powers of $z$ until the argument lies below that of $z$; this shows that $y$ is a power of $z$.

-
The application is probably to finite fields. – Qiaochu Yuan Feb 8 2011 at 19:11
Well, my point was more this: here's an example where we can see the result concretely before we go on to the general case (in the OP the field was unspecified). Sometimes (depending on the audience) this approach makes things easier. – inkspot Feb 8 2011 at 20:24