Number theory and Group theory

If we raise a number to consecutive powers one obtains certain cycles. For instance, the powers of 3 modulo 5 are 3¹ º 3        3² º 4        3³ º 2        3⁴ º 1        3⁵ º 3 Thus 3 generates a cycle of length 4 modulo 5, since when we reach the fifth power it is congruent again to 3. This means that 3 is a generator of the multiplicative group of integers modulo 5 (see section "Group, ring, field"). In general, we say that g is a primitive root modulo n if g generates a cycle of length f(n) (check section "Totient function" for more informationabout f(n). So if we keep raising g to all the powers from 1 to n-1 we will obtain f(n) different results. Using Euler¢s Totient Function, we can also say that if g is a primitive root modulo n, then f(n) has to be the smallest exponent to which g is congruent to 1 modulo n. It is important to notice that not all integers have primitive roots: there exist primitive roots modulo n if and only if n is equal to 2, 4, p^k or 2p^k where p is an odd prime. Moreover, if a number n is of this form then there are f(f(n)) primitive roots. However, given n there is no known formula or fast way to find its primitive roots. One way is to fix a certain base, which we call possible primitive root, keep raising it to increasing exponents from 1 to n-1 and check if it yields f(n) different results. The following is a better method: 1. Compute f(n). 2. Decompose f(n) into its prime factors. Then f(n) = p₁^q₁ p₂^q₂ ·s p_k^q_k . 3. Choose a possible primitive root g and keep raising it to p₁/ f(n), p₂/ f(n), etc., until p_k/ f(n). 4. If any of these values is congruent to 1 modulo n then g is not a primitive root. Otherwise it is. This way we have reduced the number of exponents that we have to try from n-1 to the number of different prime factors of f(n). However, the numbero of candidates that we have to try remains the same. The following table gives an example of the primitive roots for n smaller than 20.

We provide three different codes in order to compute primitive roots. Each one incorporates something that made the code more effectively. In the first version, the code computes the primitive roots with the very slow way: in order to find the primitive roots of n it chooses as possible candidates all numbers between 1 and n-1 and it raises each candidate to the n-1 possible exponents modulo n and checks if they are phi(n) different remainders. In the second version we apply the faster method explained in this section: instead of raising each candidate to n-1 roots, we only raise each candidate to the number of different primitive factors of n (although the number of candidates needed is the same). In order to divide each number into prime factors we do it in the classic way: trying which numbers smaller than n actually divided n. Finally, for the third version we realize that only the numbers of the form 2, 4, p^k and 2p^k have primitive roots, and hence it is not needed to find the primitive roots of the other numbers because they do not have any. We also incorporate the Sieve of Eratosthenes (see section "Totient function") in order to know which numbers are prime and to decompose each number into its prime factors.

Because there is no known formula to find the primitive roots modulo n, we want to check how do primitive roots distribute. We decided to try to divide each number into 3, 4, 5 and 6 intervals. We ran the previous code for integers up to 500, 1000 and 2000. Firstly we fixed 3 intervals and integers until 500. Then, for each number n of the form 2, 4, p^k and 2p^k from 2 to 500 we divided n into 3 intervals and we saw where the primitive roots fell. We kept adding the number of roots falling in a certain interval for every number, and finally we obtained for all the numbers until 500 how many primitive roots were in the first, second and third intervals. Then we repeated this procedure for the other number of intervals as described above. For instance, when checking 25 we would have obtained the following distribution with 5 intervals:

In this case, we would add 2 to the number of primitive roots that lie in the first interval, 1 in the second one, etc. Using this method we collected data and observed that the primitive roots were not distributed equally among the different intervals. We also noticed that the bigger the maximum number, the more significant became the difference between the intervals. The following histograms represent the total number of primitive roots for each number until 500, 1000 and 2000 for 6 intervals:

Moreover, we observed that the differences between the intervals became less relevant as the number of intervals increased. For instance, for numbers until 2000 we have the following distributions for 3, 4, 5 and 6 intervals: