# Getting primitive roots of 14

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?

-
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

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$.
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