Proving existence of primitive root $\pmod{p}$ using group theory?

Question

I'm trying to go in a kind of unconventional route and prove the existence of a primitive root $\pmod{p}$ (where $p$ is a prime) using group theory. Here's what I have so far:

By definition, $a$ is a primitive root $\pmod{p}$ if

$$a^{\phi(p)} \equiv 1 \pmod{p}$$

The set of congruence classes of integers $a \pmod{p}$ such that $gcd(a, p) = 1$ forms a group under multiplication. Every element of this group satisfies $a^{\phi(p)} \equiv 1$, by Fermat's Little Theorem.

How can I proceed with this proof? Thanks.

Answer 1

• You could use the fact that $\Bbb Z_p$ is a field, and look at the roots of the polynomial $x^{\phi(p)}-1$ over $\Bbb Z_p$. What would happen if the order of every element was smaller than $\phi(p)$? (Not sure if this is outside group theory)

Denote the elements in $\Bbb Z_p^\times$ by $a_1,\ldots,a_{p-1}$. Suppose that the order of every element is strictly less than $\phi(p)$, that is, $o(a_i)<\phi(p)$ for every $i\in\{1,\ldots,p-1\}$. Then there is an element $a_m$ with maximum order $o(a_m)=M$. Now $o(a_i)\mid M$ for every $i$. If this was not the case, then $$\text{lcm}(o(a_i),M)>M$$ and so $a_ia_m$ has order greater than $M$. This contradicts the maximality of $M$. Therefore $$x^M\equiv_p 1$$ for all elements in $\Bbb Z_p^\times$. But this is impossible since the polynomial $x^M-1$ has atmost $M$ roots over the field $\Bbb Z_p$. Therefore there exists atleast one element with order $\phi(p)$ or greater.

• Another way is to count. (This argument is due to Ireland & Rosen). Let $\psi(d)$ be the number of elements with order $d$, where $d\mid \phi(p)$. Then (since we don't count $0$) $$\sum_{d\mid \phi(p)}\psi(d)=p-1\tag{1}$$

Now, one of the properties of $\phi$, is that $$\sum_{d\mid n}\phi(d)=n\tag{2}$$

Since $(1)$ and $(2)$ are equal (choose $n=p-1=\phi(p)$), we must have $\psi=\phi$. In particular, $\psi(p-1)=\phi(p-1)>0$, so there exist a primitive root.

Answer 2

Suppose there is $K\le({\bf{Z}}/(p))^\times$ such that $K\cong C_q\times C_q$, for some prime $q$. Therefore, there are $q^2$ elements $x\in({\bf{Z}}/(p))^\times$ such that $x^q\equiv 1\pmod p$: a contradiction, because this equation has at most $q$ solutions in ${\bf{Z}}/(p)$. So, $({\bf{Z}}/(p))^\times$ does not contain any subgroup isomorphic to $C_q\times C_q$, for any prime $q$. For this characterization of the non-cyclic finite abelian groups, $({\bf{Z}}/(p))^\times$ must be cyclic.