We have natural number $m \ge 2$ which is relatively prime with integer number $g$. Let's assume that for every prime divider $q|\varphi(m) $ we have $$ g^{ \frac{\varphi(m)}{q} } \not\equiv 1 (mod \mbox{ } m).$$ Prove that $g$ is a primitive root modulo m.

($\varphi(m)$ is Euler function)

I have no idea where to start.

  • $\begingroup$ The problem has not been stated clearly. Maybe you really want to show that if $g$ is not a primitive root, then there is a prime $q$ such that $g^{\varphi(m)/q}\equiv 1$. $\endgroup$ – André Nicolas Jun 5 '16 at 20:28
  • $\begingroup$ Sorry, I have made a mistake. I have to prove that g is a primitive root. $\endgroup$ – Topolożka Jun 5 '16 at 20:32
  • $\begingroup$ Also,this command is copied from a book, I do not know how to write it differently. $\endgroup$ – Topolożka Jun 5 '16 at 20:35
  • $\begingroup$ The edit (removing the not) makes a lot of difference! And instead of "there is" one should have something like "we have" or nothing at all. $\endgroup$ – André Nicolas Jun 5 '16 at 20:57

This is a usual way to check weather $g$ is a primitive root.

To prove $g$ is a primitive root, it is equivalent to prove $\varphi(m)$ is the order of $g$ modulo $m$.

Since $\gcd(g,m)=1$, by Euler's theorem, we have $g^{\varphi(m)}\equiv 1(\mod m)$.

Now, if $g^{\frac{\varphi(m)}{p}}\neq 1(\mod m)$, then $g^d\neq 1(\mod m)$ for all $d|\varphi(m)$ and $d<\varphi(m)$. Then consider the definition of order, we get $\varphi(m)$ is the order of $g$ modulo $m$.

  • $\begingroup$ So i guess this is it ? $\endgroup$ – Topolożka Jun 5 '16 at 20:52
  • $\begingroup$ Yes. And you may figure out the details yourself. $\endgroup$ – Qingzhong Liang Jun 5 '16 at 20:56
  • $\begingroup$ If we don't get "=1 (mod m)" from any $g^{\frac{\varphi(m)}{p}}$, then we have just $g^{\varphi(m)}$ left to give us "=1 (mod m)" . Am I correct? $\endgroup$ – Topolożka Jun 5 '16 at 21:12
  • $\begingroup$ Yes, exactly. . $\endgroup$ – Qingzhong Liang Jun 5 '16 at 21:41

Coming at it from the other direction....

Consider the case where $h$, coprime to $m$, is not a primitive root $\bmod m$. Then we have some $k<\varphi(m)$ such that $h^k \equiv 1 \bmod m$. Also, we know from Euler's totient theorem that $h^{\varphi(m)} \equiv 1 \bmod m$, so certainly $ k \mid \varphi(m)$. Thus there is some $a>1$ such that $ ak = \varphi(m)$ and some prime $p$ such that $p \mid a$ ; then there is a $b$ such that $a=pb$ and $pbk = \varphi(m)$. Then

$$ h^\frac{\varphi(m)}{p} = h^{bk} = (h^k)^b \equiv 1^b \equiv 1 \bmod m $$

Therefore if we cannot find a reduced exponent of this sort for a given $g$ coprime to $m$, $g$ must be 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.