Number theory and Group theory

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.

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 k₁, k₂, etc. 3. The primitive roots of n are g^k₁ , g^k₂ , 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.

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 3¹ , 3⁷ , 3¹¹ , etc. The following picture illustrates this bijection:

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 p^k write directly the F_f(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.