2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

Hints. The primitive roots mod $p$ are exactly the generators of $(\mathbb{Z}/p\mathbb{Z})^\times\cong\mathbb{Z}/(p-1)\mathbb{Z}$. Hence, $r$ is a primitive root mod $p$ if and only if the order of $r$ is $p-1$. Besides, since $r\in(\mathbb{Z}/p\mathbb{Z})^\times$, using Lagrange's theorem the order of $r$ is a divisor of $p-1$.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Remark $ $ The claim about divisibility by deletion of prime factors is an immediate consequence of existence and uniqueness of prime factorizations. $\endgroup$ – Bill Dubuque Nov 8 '16 at 0:11

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.