proof of primitive roots algorithm

Question

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)?

Answer 1

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.