Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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

Getting primitive roots of 14.

For example, if n = 14 then the elements of Zn× are the congruence classes {1, 3, 5, 9, 11, 13}; there are φ(14) = 6 of them. The order of 1 is 1, the orders of 3 and 5 are 6, the orders of 9 and 11 are 3, and the order of 13 is 2. Thus, 3 and 5 are the primitive roots modulo 14. Question is how you get that possible candidates to primitive roots are {1, 3, 5, 9, 11, 13}?

For example which are possible candicates of primitive root of modulo 10 and how do you get them?

share|cite|improve this question
You will get a number of hints, but also note that you can write the set of congruence classes as {1, 3, 5, -5, -3, -1} and this symmetry will be there for any even $n$. This can significantly reduce the amount of arithmetic involved in testing the classes e.g. if doing them by hand in an exam. – Mark Bennet Nov 8 '11 at 14:51
up vote 2 down vote accepted

The "candidates" for the primitive roots of $\mathbb{Z}_n^*$ are all of the elements in the group. That is, all integers $0 < k < n$ such that $\gcd(n, k) = 1$.

share|cite|improve this answer
What about when getting primitive roots of some prime number such as 11? You get that 0<k<11 such that gcd(11,k)=1 $\forall k\in \{0,10\}$? Are they all candidates for the primitive roots or do you get candidates in different way when it comes to prime numbers as modulo p? – alvoutila Nov 10 '11 at 19:50
@alvoutila Certain elements, like $1$ and $p - 1$ can easily be ruled out as generators for $\mathbb{Z}_p^*$ for $p > 3$. If the ERH holds, there exist polynomial algorithms to find primitive roots modulo $p$, but I do not know how these algorithms work. As far as I'm aware, finding primitive roots of $\mathbb{Z}_p^*$ is not easy, but I am not an expert on the subject. – Zach Langley Nov 10 '11 at 21:16
Pardon my english. What does mean ERH? – alvoutila Nov 11 '11 at 13:54
ERH is short for the Extended Riemann Hypothesis. – Zach Langley Nov 11 '11 at 21:40

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.