# 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. – Hurkyl Nov 30 '14 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)$" – cansomeonehelpmeout Nov 7 '18 at 23:40

## 1 Answer

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

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