Here’s another proof.
Notice that
is a subgroup of
under multiplication modulo
Define a mapping
by
This makes sense because
by Fermat’s little theorem, so that
is clearly a homomorphism and so its image is a subgroup of
Now
consists of roots of the polynomial
of degree
in
and there cannot be more than
such roots.
.
Similarly, the kernel of
consists of roots of the polynomial
of degree
in
and so
.
Now, by the homomorphism theorem, we have
. And so we have
Therefore we actually have
i.e.
is surjective. This proves the theorem.