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

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.

• Starting with the right definition of "primitive root" would help. $a=1$, for example, satisfies your definition, but is not a primitive root.
– user14972
Nov 30, 2014 at 9:02
• A better definition would be "$a\in\Bbb Z_p$ is a primitive root if $$a^{\phi(p)}\equiv_p 1$$ and $a^k\not\equiv_p 1$ for $k<\phi(p)$" Nov 7, 2018 at 23:40

• 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.

• The order of $a_{i}a_{m}$ may not be equal to $\text{lcm}(o(a_i), M)$. Aug 18 at 23:25

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.