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 where ranges over all primitive dth roots of unity in the complex numbers. Clearly (since every root of unity is a primitive root of unity for some ). By Mobius inversion, . This means that 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 which is not a root of for d any proper divisor of n. Equivalently a generator is a root of which is not also a root of for d a proper divisor of n.
By Fermat’s Little Theorem, every unit modulo p is an nth root of unity. Since 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 has exactly roots, and none of these roots are also roots of for d a proper divisor of n. Thus all we need to do is prove that 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 , 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 ).