Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 2 down vote accepted

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.

share|cite|improve this answer
I should have known it was so simple, thank you. – D_S Oct 1 '12 at 4:32

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.