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