# Find if a number $n$ is a primitive root of $p$

Let $n = p_1\cdot p_2\cdot\ldots\cdot p_k$ where the $p_i$ are primes. Let $s = \varphi(n)$ where $\varphi$ denotes the Euler Totient Function.

If none of $p_1,p_2,\ldots,p_k$ makes $a^{(s/p_i)} = 1$ , then is $a$ a primitive root of $n$ ?

Another question is, if $g^{mk} \equiv 1 \pmod{m}$ , then does $\varphi(m)$ divides $mk$ ? If yes, why?

-
I think it's $g^{mk} \equiv 1 \pmod{m}$,not $g^mk \equiv 1 \pmod{m}$ – Next Apr 26 '13 at 10:33
Indeed. Thanks. – itamar Apr 26 '13 at 10:35

1. You need a different condition to force $a$ to be a primitive root: $a^{s/p} \neq 1 \mod n$ for any prime $p$ dividing $\phi(n)$, the order of the group $(\mathbb{Z}/n\mathbb{Z})^{\times}$.
2. Not necessarily. You only find that the order of $g$ divides $mk$. The order might be $\phi(m)$ but also might be smaller - consider $g=1,k=1$. But, if $g$ is a primitive root the result is true, since the order is $\phi(m)$.
I'll elaborate some more: if $g^{mk}=1 \mod m$, we can write $mk = q\phi(m)+r, r<\phi(m)$, we find $g^r = 1 \mod m$. Assuming $g$ is a primitive root, We must have $r=0$ since $\phi(m)$ is the order, which shows $\phi(m) | mk$.