If n has no primitive roots and a and n are coprime, what can we say about the order of a?

Question

If $n$ has no primitive roots and $a$ and $n$ are coprime, what can we say about the order of $a$? I've Googled this a bit and nothing directly comes up. Ex: if $n = 42$ then we know it has not primitive roots because it doesn't fit the form {2,4,$p^k$,$2p^k$}. If there is no primitive roots, then there are no $a$ such that the $ord_{42}(a) = 12$. Does that mean the order of $a$ has to be 1, 2, 3, 4, 6? Are we guaranteed to have orders of each or are some excluded like 12 is?

Answer 1

The group of units modulo $42$ has a structure; it just isn't cyclic. If we know its specific structure, then we can address questions about the orders of elements. Since $42=2\cdot 3\cdot7$, its units group is generated by an order $2$ element and an order $6$ element - it is isomorphic to $\mathbb{Z}/2\mathbb{Z}\times\mathbb{Z}/6\mathbb{Z}$. This group certainly has elements of orders $1,2,3$ and $6$.

Indeed, in this case, we can obtain these generators as follows: $2$ is a generator of units mod $3$, so use CRT to find a number congruent to $2 \pmod{3}$ and congruent to $1\pmod{7}$ (also to $1\pmod{2}$). We find that $29$ works.

Next, we note that $3$ is a generator mod $7$, so we seek a unit mod $42$ that is congruent to $3\pmod{7}$, and to $1\pmod{6}$. We find that $31$ works.

Thus, using $29$ as an order $2$ element, and $31$ as an order $6$ element, we can generate the whole unit group as products of powers of these two numbers: $a\equiv 29^{t_1}31^{t_2}\pmod{42}$, with $t_1\in\{0,1\}$, and $t_2\in\{0,1,2,3,4,5\}$.

---

As another example of what can happen, consider $91=7\cdot13$. We have $\phi(91)=6\cdot 12=72$, but its units group has structure $\mathbb{Z}/6\mathbb{Z}\times\mathbb{Z}/12\mathbb{Z}$, so no element has order greater than $12$. Not only is there no element of order $72$, but also the orders $36$, $24$ and $18$ are excluded.

---

In the general case, suppose $n=p_1^{a_1}\cdots p_k^{a_k}$. Then the multiplicative order modulo $p$ of a number $a$ coprime to $p$ must divide $\mathrm{lcm}\left(\phi(p_1^{a_1}),\ldots,\phi(p_k^{a_k})\right)$.