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.

  • $\begingroup$ Starting with the right definition of "primitive root" would help. $a=1$, for example, satisfies your definition, but is not a primitive root. $\endgroup$ – Hurkyl Nov 30 '14 at 9:02
  • $\begingroup$ 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)$" $\endgroup$ – cansomeonehelpmeout Nov 7 '18 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)

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


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.