Suppose $p$ is an odd prime. Prove that $r$, with $\gcd(r, p) = 1$, is a primitive root
modulo $p$ if and only if $r^{(pā1)/q}\not\equiv 1\pmod{p}$ for all prime divisors $q$ of $p ā 1$.
The only if direction is trivial, I can multiply $q$ to get $(r^{(p-1)/q})^q\equiv1^q\pmod{p}$. So, $r$ is a primitive root. How do I do the other direction? Can someone give me a hint or suggestion? Thanks
Best Answer
By definition: $\ a$ is a primitive root $\iff a\,$ has order $\,p\!-\!1.\ $ Now apply the fundamental
Order Test $\ \,a\,$ has order $\,n\iff a^n \equiv 1\,$ but $\,\color{#0a0}{a^{n/q} \not\equiv 1}\,$ for every prime $\,q\mid n$
Proof $\,\ (\Leftarrow)\,\ $ Let $\,a\,$ have $\,\color{#c00}{{\rm order}\ k}.\,$ Then $\,k\mid n\,$ (proof). $ $ If $\:k < n\,$ then $\,k\,$ is proper divisor of $\,n\,$ therefore $\,k\,$ arises by deleting at least one prime $\,q\,$ from the prime factorization of $\,n,\,$ hence $\,k\mid n/q,\,$ say $\, kj = n/q,\ $ so $\ \color{#0a0}{a^{\large n/q}} \equiv (\color{#c00}{a^{\large k}})^{\large j}\equiv \color{#c00}1^{\large j}\equiv\color{#0a0}1\,$ contra $\rm\color{#0a0}{hypothesis}$. So $\,k=n.$ $\ (\Rightarrow)\ $ Clear.