# Prove that g is a primitive root modulo m.

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.

• 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$. – André Nicolas Jun 5 '16 at 20:28
• Sorry, I have made a mistake. I have to prove that g is a primitive root. – Topolożka Jun 5 '16 at 20:32
• Also,this command is copied from a book, I do not know how to write it differently. – Topolożka Jun 5 '16 at 20:35
• 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. – 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$.

• So i guess this is it ? – Topolożka Jun 5 '16 at 20:52
• Yes. And you may figure out the details yourself. – Qingzhong Liang Jun 5 '16 at 20:56
• 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? – Topolożka Jun 5 '16 at 21:12
• Yes, exactly. . – 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.