I'm looking for a proof of this that does not rely on the Chinese remainder theorem, since the exercise is from a book that has not reached such a point (Aluffi, Algebra).

Show that for $p$ prime, the multiplicative group $G=(\mathbb{Z}/p\mathbb{Z})^*$ is cyclic. You may use that for $p$ prime, the equation $x^d=1$ has at most $d$ solutions in $\mathbb{Z}/p\mathbb{Z}$. (hint: for $g\in G$ of maximal order, $\forall h\in G, |h|\;|\;|g|$, and in particular, $h^{|g|}=1$.)

My only idea for now is constructing an element $a\in G$ such that $|a|=|G|$, using the fact that a group of order $n$ is cyclic $\iff\exists$ an element of order $n$.


If you know the structure theorem for finite Abelian groups, you will be able to prove that either a finite Abelian group $G$ is cyclic, or that its exponent is $<|G|$, that is there is $m<|G|$ with $g^m=e$ for for all $g\in G$.

An alternative attack: show that for $d\mid (p-1)$ the group $G=(\Bbb Z/\Bbb Z)^*$ has exactly $d$ solutions of $x^d\equiv1$. If you compare $G$ to $H=\Bbb Z/(p-1)\Bbb Z$, you find that the number of elements of order dividing $d$ is the same in each, therefore the number of elements of order exactly $d$ is the same in each, and now take $d=p-1$.

  • 2
    $\begingroup$ The question specifically asked for a proof that did not use the structure theorem for f.g. abelian groups (but it has been edited out after G. Sassatelli's comment). $\endgroup$ – Arnaud D. Jul 7 '17 at 12:30
  • $\begingroup$ Note that the alternative attack should be approached by induction on $d$. $\endgroup$ – Dustan Levenstein Jul 7 '17 at 12:32
  • $\begingroup$ Could you explain a bit more your alternative attack? How can I find the number of elements of order dividing $d$? $\endgroup$ – George Jul 7 '17 at 14:31
  • $\begingroup$ @George There are $\le (p-1)/d$ solutions of $x^{(p-1)/d}\equiv1$, so $\ge d$ different values of $y^{(p-1)/d}$ modulo $p$, each of which solves $y^d\equiv1$. $\endgroup$ – Lord Shark the Unknown Jul 7 '17 at 16:08

Hint: Use the hint.

Among all elements if $(\Bbb Z/p\Bbb Z)^\times$, let $g$ have maximal order, $d$. If we assume that $d<p-1$, then there exists $h\in (\Bbb Z/p\Bbb Z)^\times$ that is not among the $d$ solutions of $x^d=1$. The order $m$ of $h$ is thus not a divisor of $d$. Let $h'=h^{m/\gcd(m,d)}$. Then $h'$ is of order $m'=\frac m{\gcd(m,d)}$, which is coprime to $d$. Conclude that $hg$ has order $m'd>d$, contradiction.

  • $\begingroup$ Shouldn't $hg$ be $h'g$? $\endgroup$ – Pierre-Yves Gaillard Jul 7 '17 at 13:14
  • 1
    $\begingroup$ $m'$ might not be coprime with $d$, for instance $m=8$, $d=6$. $\endgroup$ – lhf Jul 7 '17 at 13:16
  • 1
    $\begingroup$ Isn't it enough that the order of $h$ does not divide $d$? ie: We know clearly that $(\mathbb{Z}/p\mathbb{Z})^*$ is a finite group, so the orders of all its elements is finite. If $g$ has maximal order $d$, and $d<p-1$, then $\exists h$ such that $h^d\neq 1$. But then $|h|$ does not divide $d$, and hence since it is a finite group, we get a contradiction. $\endgroup$ – George Jul 7 '17 at 18:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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