Primitive root modulo n

Elementary example

The number 3 is a primitive root modulo 7 because \begin{array}{rcrcrcrcrcr} 3^1 &=& 3^0 \times 3 &\equiv& 1 \times 3 &=& 3 &\equiv& 3 \pmod 7 \ 3^2 &=& 3^1 \times 3 &\equiv& 3 \times 3 &=& 9 &\equiv& 2 \pmod 7 \ 3^3 &=& 3^2 \times 3 &\equiv& 2 \times 3 &=& 6 &\equiv& 6 \pmod 7 \ 3^4 &=& 3^3 \times 3 &\equiv& 6 \times 3 &=& 18 &\equiv& 4 \pmod 7 \ 3^5 &=& 3^4 \times 3 &\equiv& 4 \times 3 &=& 12 &\equiv& 5 \pmod 7 \ 3^6 &=& 3^5 \times 3 &\equiv& 5 \times 3 &=& 15 &\equiv& 1 \pmod 7 \end{array}

Here we see that the period of 3k modulo 7 is 6. The remainders in the period, which are 3, 2, 6, 4, 5, 1, form a rearrangement of all nonzero remainders modulo 7, implying that 3 is indeed a primitive root modulo 7. This derives from the fact that a sequence (gk modulo n) always repeats after some value of k, since modulo n produces a finite number of values. If g is a primitive root modulo n and n is prime, then the period of repetition is n − 1. Permutations created in this way (and their circular shifts) have been shown to be Costas arrays.

Definition

If n is a positive integer, the integers from 1 to n − 1 that are coprime to n (or equivalently, the congruence classes coprime to n) form a group, with multiplication modulo n as the operation; it is denoted by \mathbb{Z}, and is called the group of units modulo n, or the group of primitive classes modulo n. As explained in the article multiplicative group of integers modulo n, this multiplicative group (\mathbb{Z}) is cyclic if and only if n is equal to 2, 4, p, or 2p where p is a power of an odd prime number. When (and only when) this group \mathbb{Z} is cyclic, a generator of this cyclic group is called a primitive root modulo n (or in fuller language primitive root of unity modulo n, emphasizing its role as a fundamental solution of the roots of unity polynomial equations X − 1 in the ring \mathbb{Z}), or simply a primitive element of \mathbb{Z}.

When \mathbb{Z} is non-cyclic, such primitive elements mod n do not exist. Instead, each prime component of n has its own sub-primitive roots (see 15 in the examples below).

For any n (whether or not \mathbb{Z} is cyclic), the order of \mathbb{Z} is given by Euler's totient function φ(n) . And then, Euler's theorem says that aφ(n) ≡ 1 (mod n) for every a coprime to n; the lowest power of a that is congruent to 1 modulo n is called the multiplicative order of a modulo n. In particular, for a to be a primitive root modulo n, aφ(n) has to be the smallest power of a that is congruent to 1 modulo n.

Examples

For example, if then the elements of \mathbb{Z} are the congruence classes {1, 3, 5, 9, 11, 13}; there are of them. Here is a table of their powers modulo 14:

x x, x2, x3, ... (mod 14) 1 : 1 3 : 3, 9, 13, 11, 5, 1 5 : 5, 11, 13, 9, 3, 1 9 : 9, 11, 1 11 : 11, 9, 1 13 : 13, 1

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.

For a second example let The elements of \mathbb{Z} are the congruence classes {1, 2, 4, 7, 8, 11, 13, 14}; there are of them.

x x, x2, x3, ... (mod 15) 1 : 1 2 : 2, 4, 8, 1 4 : 4, 1 7 : 7, 4, 13, 1 8 : 8, 4, 2, 1 11 : 11, 1 13 : 13, 4, 7, 1 14 : 14, 1

Since there is no number whose order is 8, there are no primitive roots modulo 15. Indeed, , where λ is the Carmichael function.

Table of primitive roots

Numbers n that have a primitive root are of the shape :n \in {1, 2, 4, p^k, 2 \cdot p^k ; ; | ; ; 2 := {1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 17, 18, 19, ...}. These are the numbers n with \varphi(n) = \lambda(n), kept also in the sequence in the OEIS.

The following table lists the primitive roots modulo n up to n=31:

Properties

Gauss proved that for any prime number p (with the sole exception of the product of its primitive roots is congruent to 1 modulo p.

He also proved that for any prime number p, the sum of its primitive roots is congruent to μ(p − 1) modulo p, where μ is the Möbius function.

For example, :{|

E.g., the product of the latter primitive roots is 2^6\cdot 3^4\cdot 7\cdot 11^2\cdot 13\cdot 17 = 970377408 \equiv 1 \pmod{31}, and their sum is 123 \equiv -1 \equiv \mu(31-1) \pmod{31}.

If a is a primitive root modulo the prime p, then a^\frac{p-1}{2}\equiv -1 \pmod p.

Artin's conjecture on primitive roots states that a given integer a that is neither a perfect square nor −1 is a primitive root modulo infinitely many primes.

Finding primitive roots

No simple general formula to compute primitive roots modulo n is known. There are however methods to locate a primitive root that are faster than simply trying out all candidates. If the multiplicative order (its exponent) of a number m modulo n is equal to \varphi(n) (the order of \mathbb{Z}), then it is a primitive root. In fact the converse is true: If m is a primitive root modulo n, then the multiplicative order of m is \varphi(n) = \lambda(n)~. We can use this to test a candidate m to see if it is primitive.

For n 1 first, compute \varphi(n)~. Then determine the different prime factors of \varphi(n), say p1, ..., p. Finally, compute :g^{\varphi(n)/p_i}\bmod n \qquad\mbox{ for } i=1,\ldots,k using a fast algorithm for modular exponentiation such as exponentiation by squaring. A number g for which these k results are all different from 1 is a primitive root.

The number of primitive roots modulo n, if there are any, is equal to :\varphi\left(\varphi(n)\right) since, in general, a cyclic group with r elements has \varphi(r) generators.

For prime n, this equals \varphi(n-1), and since n / \varphi(n-1) \in O(\log\log n) the generators are very common among {2, ..., n−1} and thus it is relatively easy to find one.

If g is a primitive root modulo p, then g is also a primitive root modulo all powers p unless gp−1 ≡ 1 (mod p2); in that case, g + p is.

If g is a primitive root modulo p, then g is also a primitive root modulo all smaller powers of p.

If g is a primitive root modulo p, then either g or g + p (whichever one is odd) is a primitive root modulo 2p.

Finding primitive roots modulo p is also equivalent to finding the roots of the (p − 1)st cyclotomic polynomial modulo p.

Order of magnitude of primitive roots

The least primitive root g modulo p (in the range 1, 2, ..., p − 1) is generally small.

Upper bounds

Burgess (1962) proved that for every ε 0 there is a C such that g_p \leq C,p^{\frac{1}{4}+\varepsilon}.

Grosswald (1981) proved that if p e^{e^{24}} \approx 10^{11504079571}, then g_p

Shoup (1990, 1992) proved, assuming the generalized Riemann hypothesis, that

Lower bounds

Fridlander (1949) and Salié (1950) proved that there is a positive constant C such that for infinitely many primes g C log p.

It can be proved in an elementary manner that for any positive integer M there are infinitely many primes such that M

Applications

A primitive root modulo n is often used in pseudorandom number generators and cryptography, including the Diffie–Hellman key exchange scheme. Sound diffusers have been based on number-theoretic concepts such as primitive roots and quadratic residues.

Footnotes

References

Sources

• {{cite book

• {{cite journal

The Disquisitiones Arithmeticae has been translated from Gauss's Ciceronian Latin into English and German. The German edition includes all of his papers on number theory: all the proofs of quadratic reciprocity, the determination of the sign of the Gauss sum, the investigations into biquadratic reciprocity, and unpublished notes.

• {{cite book | translator-last = Clarke | translator-first = Arthur A. | orig-year = 1801 | year = 1986

• {{cite book | translator-last = Maser | translator-first = H. | orig-year = 1801 | year = 1965 | trans-title = Studies of Higher Arithmetic

• {{cite book

• {{cite book | author-link = Ivan Matveyevich Vinogradov | chapter-url = https://books.google.com/books?id=xlIfdGPM9t4C&pg=PA105

• {{cite journal | author1-link = Joachim von zur Gathen

References

1. "Primitive root - Encyclopedia of Mathematics".
2. {{Harv. Vinogradov. 2003
3. {{Harv. Gauss. 1986
4. Stromquist, Walter. "What are primitive roots?". Bryn Mawr College.
5. {{Harvnb. Vinogradov. 2003
6. {{Harvnb. Vinogradov. 2003
7. {{Harvnb. Gauss. 1986
8. {{Harvnb. Gauss. 1986
9. {{Harvnb. Gauss. 1986
10. {{OEIS. A010554
11. Burgess, D. A.. (1962). "On Character Sums and Primitive Roots †". [[Proceedings of the London Mathematical Society]].
12. Grosswald, E.. (1981). "On Burgess' Bound for Primitive Roots Modulo Primes and an Application to Γ(p)". [[American Journal of Mathematics]].
13. {{Harvnb. Bach. Shallit. 1996
14. Gentle, James E.. (2003). "Random number generation and Monte Carlo methods". Springer.
15. (2015). "Least Prime Primitive Roots". International Journal of Mathematics and Computer Science.
16. (1993). "A Course in Computational Algebraic Number Theory". [[Springer Science+Business Media.
17. Feldman, Eliot. (July 1995). "A reflection grating that nullifies the specular reflection: A cone of silence". J. Acoust. Soc. Am..
18. Knuth, Donald E.. (1998). "Seminumerical Algorithms". Addison–Wesley.
19. Ribenboim, Paulo. (1996). "The New Book of Prime Number Records". [[Springer Science+Business Media.
20. Walker, R.. (1990). "The design and application of modular acoustic diffusing elements". [[British Broadcasting Corporation]].