# Characterization of primitive roots modulo a prime

Let $p$ be a prime. Given a divisor $d$ of $p-1$, there always exist numbers with multiplicative order $d$ modulo $p$, and there are $\phi(d)$ such numbers. If for example $a$ has order $d$, then $a, a^2, ... , a^{d-1}$ are $d-1$ noncongruent elements whose $d$th power is congruent to $1$, with $a^t$ having order $d$ if and only if $(t,d) = 1$. Since the polynomial $x^d-1$ has at most $d$ roots in $\mathbb{Z_p}$, no more elements with order $d$ will be found besides those mentioned.

Now let $p-1 = q_1^{e_1}\cdots q_r^{e_r}$ with $q_i$ prime. If for each $1 \leq i \leq r$ you let $a_i$ be an integer with order $q_i^{e_i}$, since $\mathbb{U(Z_p)}$ is an abelian group, the order of the product $a_1\cdots a_r$ will be the product of the relatively prime orders $q_1^{e_1}, q_2^{e_2},$ etc. In other words $a_1\cdots a_r$ will be a primitive root modulo $p$.

My question is, do all primitive roots look like this, i.e. a product of $r$ elements with orders of maximal prime powers? It seems this should be the case, since there are $\phi(q_i^{e_i})$ possibilities for elements with order $q_i^{e_i}$, making for $\phi(p-1) = \phi(q_1^{e_1})\phi(q_2^{e_2})\cdots$ combinations of products, all of which are primitive roots. While it can be shown that there are $\phi(p-1)$ primitive roots modulo $p$, this doesn't immediately imply that each primitive root is congruent to such a combination--I still would like to prove that two distinct products are noncongruent modulo $p$, i.e. if $a_1, a_1'$ are noncongruent with order $q_1^{e_1}$, and $a_2, a_2'$ are noncongruent with order $q_2^{e_2}$, etc. then $a_1a_2 \cdots a_r$ and $a_1'a_2'\cdots a_r'$ are primitive roots modulo $p$ which are noncongruent. Any ideas?

-

The primitive roots of $p$ are indeed all (congruent to) a product of numbers $b_i$, where $b_i$ has order $q_i^{e_i}$. We can say a little more.
Let $g=a_1a_2\cdots a_r$ as in your question. So the $a_i$ have order $q_i^{e_i}$ modulo $p$.
Then any primitive root of $p$ is congruent to $g^t$, for some $t$ relatively prime to $p-1$. Moreover, up to congruence modulo $p$, all primitive roots of $p$ are obtainable in this way.
Thus if $h$ is a primitive root of $p$, then $$h\equiv a_1^ta_2^t\cdots a_r^t\pmod{p},$$ for some $t$ relatively prime to $q_1^{e_1}q_2^{e_2}\cdots q_r^{e_r}$.
But then for any $i$, $t$ is relatively prime to $q_i^{e_i}$, and therefore $a_i^t$ has order $q_i^{e_i}$ modulo $p$. Now just let $b_i=a_i^t$, and we have the desired result.