0
$\begingroup$

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?

  • 0
    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.2011-11-08

1 Answers 1

1

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

  • 0
    ERH is short for the Extended Riemann Hypothesis.2011-11-11