In my book (Elementary Number Theory, Stillwell), exercise 3.9.1 asks to give an alternative proof of the existence of a primitive root for any prime.

Let $p$ be prime, and consider the group $\mathbb{Z}/p\mathbb{Z}$.

Suppose that the non-zero elements $\text{mod}\ p$ have maximum order $n < p - 1$. Show that this implies $x^n \equiv 1 \ (\text{mod}\ p)$ for all the $p - 1$ non-zero values of $x$, $\text{mod}\ p$, contrary to Lagrange's polynomial congruence theorem.

What I've considered so far is that all non-zero elements of the group $\mathbb{Z}/p\mathbb{Z}$ generate subgroups of order $k \leq n < p - 1$, such that $k \mid p - 1$ (by Lagrange's theorem for groups). Showing that $k \mid n$ eludes me however. Any further ideas?


Let $n$ be the maximum order. To prove that $x^n\equiv 1\pmod{p}$, it is enough to show that the order of $x$ divides $n$.

Let $a$ be an element of maximum order, and suppose that the order $m$ of $x$ does not divide $n$. Then the lcm $\ell$ of $m$ and $n$ is greater than $n$. We show that there is an element of order $\ell$, contradicting the maximality of $n$.

By considering the prime power factorization of $m$ and $n$, we can find $m'$, $n'$ such that $m'$ divides $m$, and $n'$ divides $n$, and $\gcd(m',n')=1$, and $m'n'=\ell$.

Using $x$, we can construct an element of order $m'$, and using $a$ we can construct an element of order $n'$. But since $\gcd(m',n')=1$, we can construct an element of order $m'n'$, and we are finished.

Added: The following standard result was used in the construction:

Lemma: If $a$ has order $h$ modulo $p$, and $b$ has order $k$, where $\gcd(h,k)=1$, then $ab$ has order $hk$.

Proof: Let $r$ be the order of $ab$. Since $(ab)^{hk}\equiv 1\pmod{p}$, it follows that $r$ divides $hk$. We will show that $hk$ divides $r$.

Note that since $b^k\equiv 1$, we have $$a^{rk}\equiv a^{rk}b^{rk}\equiv 1\pmod{p}.$$ It follows that $h$ divides $rk$. Since $\gcd(h,k)=1$, it follows that $h$ divides $r$. Similarly, $k$ divides $r$. But since $\gcd(h,k)=1$, it follows that $hk$ divides $r$. This completes the proof.

  • $\begingroup$ Interesting. I never thought of an approach this way. Thank you. I wonder if a proof other than by contradiction exists? Probably not, but oh well. $\endgroup$ – Noldorin May 24 '14 at 13:40
  • $\begingroup$ You are welcome. I had thought that of a proof along these lines as the standard one. I expect that in this case proof by contradiction can be avoided. $\endgroup$ – André Nicolas May 24 '14 at 14:16
  • $\begingroup$ Ah fair enough. :) I'm not sure myself how you could avoid a contradiction argument here, but I'll take your word for it! $\endgroup$ – Noldorin May 24 '14 at 17:41
  • 1
    $\begingroup$ OK, tomorrow. Wine, song, and mathematics make an uneasy mixture. I am very far from being a Banach. $\endgroup$ – André Nicolas May 25 '14 at 2:30
  • 1
    $\begingroup$ I added to the answer. I think it is what you were wondering about. Please correct me if it is something else. $\endgroup$ – André Nicolas May 25 '14 at 15: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.