We know the following from elementary number theory:

(1) for $gcd(a,n) =1, a^{\phi(n)} \equiv 1 (mod \, n)$

(2) $ord_na \mid \phi(n)$

(3) $a$ is a primitive root $mod \, n$ iff $ord_na = \phi(n)$.

From (2), the only possible values of $ord_ma$ are divisors of $\phi(n)$. So, to exclude $a$ as a primitive root $mod \,n$, it suffices to test if for any proper divisor of $\phi(n)$, say $k\,, a^k \equiv 1 \,(mod \,n$.

Now let's choose an arbitrary $\phi(n)$, with prime factorization $p_1p_2p_3.$ The $p$'s can be the same or different. The set of the proper divisors of $\phi(n)$ is $\{p_1, \,\,p_2, \, p_3, \,p_1p_2, \,p_1p_3,\, p_2p_3\}$. If $a^{p_1} \equiv 1 \pmod n$, then there's no need to test $p_1p_2, \, p_1p_3\,$, e.g., $\,(a^{p_1})^{p_2} \equiv 1 \pmod n$. It seems at least intuitive that the test set only has to include the PRIME divisors of $\phi(n)$.

Can anyone help formalize the latter paragraph into a proof (or has this already been done)?

  • $\begingroup$ Why couldn't the order be $p_1p_2$? $\endgroup$ – lulu Apr 29 '17 at 18:48
  • $\begingroup$ For example, $n=16$ has no primitive root, but the order of $3\pmod {16}$ is $4$, not $2$. $\varphi(16)=8$ so if you only tested the primes, you'd incorrectly conclude that $3$ was a primitive root. $\endgroup$ – lulu Apr 29 '17 at 19:20
  • $\begingroup$ do you have a counterexample where $n$ is prime? $\endgroup$ – doctorjay Apr 29 '17 at 20:38
  • $\begingroup$ Well, every prime has a primitive root, of course. Do you mean "is there an example where the order of an element, not a primitive root, mod $p$ is not itself a prime?" The answer is, of course. $4$ has order $9\pmod {19}$ for example. To produce examples, just take a primitive root $\pmod p$ and raise it to an appropriate power. $\endgroup$ – lulu Apr 29 '17 at 20:43
  • $\begingroup$ I neglected to specify, but the algorithm in question is assuming that the modulus is prime. $\endgroup$ – doctorjay Apr 29 '17 at 20:45

All of the following presupposes $gcd(a, n) \equiv 1$

Let $d$ be a divisor of $\phi(n)$ such that $a^d \equiv 1 \pmod n. $ If $d = \phi(n)/p^{*}$, where $p^*$ is a prime factor of $\phi(n)$, then $a$ is not a primitive root $\pmod n$ and we are done.

Otherwise, write $d=(p_1p_2...p_k)$, where the factors $p$ are not necessarily unique. Write $\phi(n)$ as $d \cdot q^*$, where $q^*= (q_1q_2...q_k)$ where the factors $q$ are not necessarily unique.

Choose an arbitrary single prime factor of $\phi(n),\; q,$ from $q^*$ and write $\phi(n)=d \cdot q \cdot \frac{q^*}{q}$. Therefore, $\frac{\phi(n)}{q} = d \cdot \frac{q^*}{q}$.

From the specification of $d, \; a^{\frac{\phi(n)}{q}} = a^{d \cdot \frac{q*}{q}}=(a^d)^{\frac{q*}{q}} \equiv 1 \pmod n.$ So for any divisor of $\phi(n)$ that shows $a$ not to be a primitive root, there exists at least one prime factor of $\phi(n)$ such that $a^{\frac{\phi(n)}{q}} \equiv 1 \pmod n$, thereby demonstrating the same. Therefore, the maximal calculation necessary to determine if $a$ is a primitive root$\pmod n$ is to calculate $a^{\frac{\phi(n)}{p_i}} \pmod n$ for each of the distinct prime factors, $p_i$, of $\phi(n)$. Obviously, you can stop as soon as you return 1.

Here's a graphic illustration of an example. We are choosing the prime factorization of $\phi(n)$ to be $pqrs$, where $p, q, r, s$ are distinct primes. The function $f(x)$ is a Boolean function evaluating the truth value of $a^x \equiv 1 \pmod n$.

The columns of the table represent the set of variables based on the distinct prime factors that need to be evaluated and the rows represent all the divisors of $\phi(n)$, excluding 1 and $\phi(n)$ itself. $T$ at an intersection indicates that the column value stands as a witness for the row value, i.e., if the column value is true then the row value is true. $$ \begin{bmatrix} \cdot & \small{f(\frac{\phi(n)}{s})=f(pqr)} & \small{f(\frac{\phi(n)}{r})=f(pqs)} & \small{f(\frac{\phi(n)}{q})=f(prs)} & \small{f(\frac{\phi(n)}{p})=f(qrs)}\\ f(p) & T & T & T & F \\ f(q) & T & T & F & T \\ f(p) & T & T & T & F \\ f(s) & F & T & T & T \\ f(pq) & T & T & F & F \\ f(pr) & T & F & T & F \\ f(ps) & F & T & T & F \\ f(qr) & T & F & F & T \\ f(qs) & F & T & F & T \\ f(rs) & F & F & T & T \\ f(pqr) & T & F & F & F \\ f(pqs) & F & T & F & F \\ f(prs) & F & F & T & F \\ f(qrs) & F & F & F & T \\ \end{bmatrix} $$ The important thing to note is that every row has at least one $T$ value, which is the same as saying every divisor of $\phi(n)$ that shows $a$ not to be a primitive root has at least 1 $a^{\frac{\phi(n)}{p^*}} \equiv 1 \pmod n$. A similar construction can be made if the prime factors of $\phi(n)$ are not distinct, and yields a similar result.

  • $\begingroup$ A working JavaScript application implementing this algorithm is here $\endgroup$ – doctorjay May 2 '17 at 17:10

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.