Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
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$.
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.
