0
$\begingroup$

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

  • 0
    @ArturoMagidin, thanks for the latex tip!2012-02-01

1 Answers 1

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

  • 0
    ah, yes, thank you for that.2012-02-01