Let $p$ be an odd prime. How can Ihow that $a$ is a primitive root modulo $p$ iff $a^{(p-1)/q}\ncong 1 \pmod{p}$ for all prime divisors $q$ of $p-1$. Thanks
A question on primitive roots
0
$\begingroup$
number-theory
elementary-number-theory
-
0@ArturoMagidin, thanks for the latex tip! – 2012-02-01
1 Answers
5
I hope you can see one direction: if $a^{(p-1)/q}\equiv1\pmod p$ then $a$ is not a primitive root.
Now suppose $a$ is not a primitive root. Then $a^d\equiv1\pmod p$ for some proper divisor $d$ of $p-1$. So all you have to show is that every proper divisor of $p-1$ is a divisor of $(p-1)/q$ for some prime divisor $q$ of $p-1$.
-
0ah, yes, thank you for that. – 2012-02-01