LaTeX4Web 1.4 OUTPUT In this section we compare the generators described in "Group, ring, field" and the primitive roots described in "Primitive roots". It turns out that we can apply a bijection between the primitive roots of n and the generators of f(n). Firstly, this means that the number of primitive roots of n is exactly the number of generators of f(n). Secondly, this bijection is actually called a isomorphism. An ismorphism is a map between two algebraic structures of the same type (in this case two groups) and that admits an inverse.
LaTeX4Web 1.4 OUTPUT The way to do so is the following one:
1. We want to find all the primitive roots modulo n. We only find one, which we call g.
2. We compute f(n) and find the numbers coprime to f(n), namely k1, k2, etc.
3. The primitive roots of n are gk1 , gk2 , etc. modulo n.
It is interesting to notice that the distribution of the generators is symmetrical, because if a is a generator, -a is also a generator. Similarly, if g is a primitive root, 1/g is also a primitive root. However, when we apply the isomorphism from the generators to the primitive roots, we lose this symmetry.
LaTeX4Web 1.4 OUTPUT For example, imagine that we want to find the primitive roots of 31. We compute f(31)=30. Now we find the generators of 30 (the numbers coprime to 30): 1, 7, 11, 13, 17, 19, 23, 29. We only need to find one primitive root of 31. Say we find 3. Then, the primitive roots of 31 are 31 , 37 , 311 , etc. The following picture illustrates this bijection:
LaTeX4Web 1.4 OUTPUT Therefore, with the information explained in this section and in "Primitive root", "First primitive root" and "Cyclotomic polynomials" we propose the following way for finding primitive roots:
1. Compute f(n). If f(n) is of the form p, 2p or pk write directly the Ff(n)(x) cyclotomic polynomial and evaluate it for all the numbers between 2 and n-1. If when evaluating a certain integer the polynomial returns 0 \textitmodulo n, then this integer is a primitive root. After finding f(n) primitive roots, stop and these are them all.
2. If f(n) is not of the form described before, start trying possible candidates to primitive roots either with 2 (since between 1 and 10 the probabilities of finding a primitive root are very high) or in the interval between n/2 and 3n/4 (since we have seen that there is a higher density of primitive roots). To check if the number is a primitive root apply the method explained in section 2. In average it will only be needed to raise the candidate to two exponents to see if it is a primitive root or not (since the average number of different prime factors of integers below 2000 is 2,29).
3. After having found one primitive root g, compute f(n) and find the numbers that are coprime to it. Then keep raising g to all the numbers coprime to f(n) modulo n and this provides all the other primitive roots.

Here you can find two codes: the first one computes for each integer n the number of different prime factors of n. This was used to obtain the 2,29. The second one allows the user to rapidly make the bijection between the generators and the primitive roots.

PrimeFactors.txt PrimeFactors.txt
Size : 1.231 Kb
Type : txt
Map.txt Map.txt
Size : 0.408 Kb
Type : txt