Menu
Home Explore People Places Arts History Plants & Animals Science Life & Culture Technology
On this page
Primitive root modulo n
Generator of the multiplicative group of integers modulo n

In modular arithmetic, a number g is a primitive root modulo n if every number a coprime to n is congruent to a power of g modulo n. That is, g is a primitive root modulo n if for every integer a coprime to n, there is some integer k for which gk ≡ a (mod n). Such a value k is called the index or discrete logarithm of a to the base g modulo n. So g is a primitive root modulo n if and only if g is a generator of the multiplicative group of integers modulo n.

Gauss defined primitive roots in Article 57 of the Disquisitiones Arithmeticae (1801), where he credited Euler with coining the term. In Article 56 he stated that Lambert and Euler knew of them, but he was the first to rigorously demonstrate that primitive roots exist for a prime n. In fact, the Disquisitiones contains two proofs: The one in Article 54 is a nonconstructive existence proof, while the proof in Article 55 is constructive.

A primitive root exists if and only if n is 1, 2, 4, pk or 2pk, where p is an odd prime and k > 0. For all other values of n the multiplicative group of integers modulo n is not cyclic. This was first proved by Gauss.

We don't have any images related to Primitive root modulo n yet.
We don't have any YouTube videos related to Primitive root modulo n yet.
We don't have any PDF documents related to Primitive root modulo n yet.
We don't have any Books related to Primitive root modulo n yet.
We don't have any archived web articles related to Primitive root modulo n yet.

Elementary example

The number 3 is a primitive root modulo 75 because 3 1 = 3 0 × 3 ≡ 1 × 3 = 3 ≡ 3 ( mod 7 ) 3 2 = 3 1 × 3 ≡ 3 × 3 = 9 ≡ 2 ( mod 7 ) 3 3 = 3 2 × 3 ≡ 2 × 3 = 6 ≡ 6 ( mod 7 ) 3 4 = 3 3 × 3 ≡ 6 × 3 = 18 ≡ 4 ( mod 7 ) 3 5 = 3 4 × 3 ≡ 4 × 3 = 12 ≡ 5 ( mod 7 ) 3 6 = 3 5 × 3 ≡ 5 × 3 = 15 ≡ 1 ( mod 7 ) {\displaystyle {\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 Z {\displaystyle \mathbb {Z} } ×n, 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 ( Z {\displaystyle \mathbb {Z} } ×n) is cyclic if and only if n is equal to 2, 4, pk, or 2pk where pk is a power of an odd prime number.678 When (and only when) this group Z {\displaystyle \mathbb {Z} } ×n is cyclic, a generator of this cyclic group is called a primitive root modulo n9 (or in fuller language primitive root of unity modulo n, emphasizing its role as a fundamental solution of the roots of unity polynomial equations Xm − 1 in the ring Z {\displaystyle \mathbb {Z} } n), or simply a primitive element of Z {\displaystyle \mathbb {Z} } ×n.

When Z {\displaystyle \mathbb {Z} } ×n 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 Z {\displaystyle \mathbb {Z} } ×n is cyclic), the order of Z {\displaystyle \mathbb {Z} } ×n is given by Euler's totient function φ(n) (sequence A000010 in the OEIS). 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 n = 14 then the elements of Z {\displaystyle \mathbb {Z} } ×n are the congruence classes {1, 3, 5, 9, 11, 13}; there are φ(14) = 6 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 n = 15 . The elements of Z {\displaystyle \mathbb {Z} } ×15 are the congruence classes {1, 2, 4, 7, 8, 11, 13, 14}; there are φ(15) = 8 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, λ(15) = 4, where λ is the Carmichael function. (sequence A002322 in the OEIS)

Table of primitive roots

Numbers n {\displaystyle n} that have a primitive root are of the shape

n ∈ { 1 , 2 , 4 , p k , 2 ⋅ p k | 2 < p  prime ; k ∈ N } , {\displaystyle n\in \{1,2,4,p^{k},2\cdot p^{k}\;\;|\;\;2<p{\text{ prime}};\;k\in \mathbb {N} \},} = {1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 17, 18, 19, ...}.10

These are the numbers n {\displaystyle n} with φ ( n ) = λ ( n ) , {\displaystyle \varphi (n)=\lambda (n),} kept also in the sequence A033948 in the OEIS.

The following table lists the primitive roots modulo n up to n = 31 {\displaystyle n=31} :

⁠ n {\displaystyle n} ⁠primitive roots modulo ⁠ n {\displaystyle n} ⁠order φ ( n ) , {\displaystyle \varphi (n),} (OEIS: A000010)exponent λ ( n ) , {\displaystyle \lambda (n),} (OEIS: A002322)
1011
2111
3222
4322
52, 344
6522
73, 566
842
92, 566
103, 744
112, 6, 7, 81010
1242
132, 6, 7, 111212
143, 566
1584
1684
173, 5, 6, 7, 10, 11, 12, 141616
185, 1166
192, 3, 10, 13, 14, 151818
2084
21126
227, 13, 17, 191010
235, 7, 10, 11, 14, 15, 17, 19, 20, 212222
2482
252, 3, 8, 12, 13, 17, 22, 232020
267, 11, 15, 191212
272, 5, 11, 14, 20, 231818
28126
292, 3, 8, 10, 11, 14, 15, 18, 19, 21, 26, 272828
3084
313, 11, 12, 13, 17, 21, 22, 243030

Properties

Gauss proved11 that for any prime number p (with the sole exception of p = 3), the product of its primitive roots is congruent to 1 modulo p.

He also proved12 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,

p = 3,μ(2) = −1.The primitive root is 2.
p = 5,μ(4) = 0.The primitive roots are 2 and 3.
p = 7,μ(6) = 1.The primitive roots are 3 and 5.
p = 31,μ(30) = −1.The primitive roots are 3, 11, 12, 13, 17, 21, 22 and 24.

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

If a {\displaystyle a} is a primitive root modulo the prime p {\displaystyle p} , then a p − 1 2 ≡ − 1 ( mod p ) {\displaystyle 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.1314 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 φ ( n ) {\displaystyle \varphi (n)} (the order of Z {\displaystyle \mathbb {Z} } ×n), 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 φ ( n ) = λ ( n )   . {\displaystyle \varphi (n)=\lambda (n)~.} We can use this to test a candidate m to see if it is primitive.

For n > 1 {\displaystyle n>1} first, compute φ ( n )   . {\displaystyle \varphi (n)~.} Then determine the different prime factors of φ ( n ) {\displaystyle \varphi (n)} , say p1, ..., pk. Finally, compute

g φ ( n ) / p i mod n  for  i = 1 , … , k {\displaystyle 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 to15

φ ( φ ( n ) ) {\displaystyle \varphi \left(\varphi (n)\right)}

since, in general, a cyclic group with r elements has φ ( r ) {\displaystyle \varphi (r)} generators.

For prime n, this equals φ ( n − 1 ) {\displaystyle \varphi (n-1)} , and since n / φ ( n − 1 ) ∈ O ( log ⁡ log ⁡ n ) {\displaystyle 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.16

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

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

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

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 gp modulo p (in the range 1, 2, ..., p − 1) is generally small.

Upper bounds

Burgess (1962) proved1920 that for every ε > 0 there is a C such that g p ≤ C p 1 4 + ε . {\displaystyle g_{p}\leq C\,p^{{\frac {1}{4}}+\varepsilon }.}

Grosswald (1981) proved2122 that if p > e e 24 ≈ 10 11504079571 {\displaystyle p>e^{e^{24}}\approx 10^{11504079571}} , then g p < p 0.499 . {\displaystyle g_{p}<p^{0.499}.}

Shoup (1990, 1992) proved,23 assuming the generalized Riemann hypothesis, that gp = O(log6 p).

Lower bounds

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

It can be proved25 in an elementary manner that for any positive integer M there are infinitely many primes such that M < gp < p − M.

Applications

A primitive root modulo n is often used in pseudorandom number generators26 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.2728

See also

Footnotes

Sources

  • Bach, Eric; Shallit, Jeffrey (1996). Efficient Algorithms. Algorithmic Number Theory. Vol. I. Cambridge, MA: The MIT Press. ISBN 978-0-262-02405-1.
  • Carella, N. A. (2015). "Least Prime Primitive Roots". International Journal of Mathematics and Computer Science. 10 (2): 185–194. arXiv:1709.01172.

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.

  • Gauss, Carl Friedrich (1986) [1801]. Disquisitiones Arithmeticae. Translated by Clarke, Arthur A. (2nd, corrected ed.). New York, NY: Springer. ISBN 978-0-387-96254-2.
  • Gauss, Carl Friedrich (1965) [1801]. Untersuchungen über höhere Arithmetik [Studies of Higher Arithmetic] (in German). Translated by Maser, H. (2nd ed.). New York, NY: Chelsea. ISBN 978-0-8284-0191-3.

Further reading

References

  1. Weisstein, Eric W. "Modulo Multiplication Group". MathWorld. /wiki/Eric_W._Weisstein ↩

  2. "Primitive root - Encyclopedia of Mathematics". encyclopediaofmath.org. Retrieved 2024-11-05. https://encyclopediaofmath.org:443/wiki/Primitive_root ↩

  3. (Vinogradov 2003, pp. 105–121, § VI PRIMITIVE ROOTS AND INDICES) - Vinogradov, I.M. (2003). "§ VI Primitive roots and indices". Elements of Number Theory. Mineola, NY: Dover Publications. pp. 105–121. ISBN 978-0-486-49530-9. https://books.google.com/books?id=xlIfdGPM9t4C&pg=PA105 ↩

  4. (Gauss 1986, arts. 52–56, 82–891) - Gauss, Carl Friedrich (1986) [1801]. Disquisitiones Arithmeticae. Translated by Clarke, Arthur A. (2nd, corrected ed.). New York, NY: Springer. ISBN 978-0-387-96254-2. ↩

  5. Stromquist, Walter. "What are primitive roots?". Mathematics. Bryn Mawr College. Archived from the original on 2017-07-03. Retrieved 2017-07-03. https://web.archive.org/web/20170703173446/http://www.brynmawr.edu/math/people/stromquist/numbers/primitive.html ↩

  6. Weisstein, Eric W. "Modulo Multiplication Group". MathWorld. /wiki/Eric_W._Weisstein ↩

  7. "Primitive root - Encyclopedia of Mathematics". encyclopediaofmath.org. Retrieved 2024-11-05. https://encyclopediaofmath.org:443/wiki/Primitive_root ↩

  8. Vinogradov 2003, pp. 105–121, § VI Primitive roots and indices. - Vinogradov, I.M. (2003). "§ VI Primitive roots and indices". Elements of Number Theory. Mineola, NY: Dover Publications. pp. 105–121. ISBN 978-0-486-49530-9. https://books.google.com/books?id=xlIfdGPM9t4C&pg=PA105 ↩

  9. Vinogradov 2003, p. 106. - Vinogradov, I.M. (2003). "§ VI Primitive roots and indices". Elements of Number Theory. Mineola, NY: Dover Publications. pp. 105–121. ISBN 978-0-486-49530-9. https://books.google.com/books?id=xlIfdGPM9t4C&pg=PA105 ↩

  10. Gauss 1986, art 92. - Gauss, Carl Friedrich (1986) [1801]. Disquisitiones Arithmeticae. Translated by Clarke, Arthur A. (2nd, corrected ed.). New York, NY: Springer. ISBN 978-0-387-96254-2. ↩

  11. Gauss 1986, arts. 80. - Gauss, Carl Friedrich (1986) [1801]. Disquisitiones Arithmeticae. Translated by Clarke, Arthur A. (2nd, corrected ed.). New York, NY: Springer. ISBN 978-0-387-96254-2. ↩

  12. Gauss 1986, art 81. - Gauss, Carl Friedrich (1986) [1801]. Disquisitiones Arithmeticae. Translated by Clarke, Arthur A. (2nd, corrected ed.). New York, NY: Springer. ISBN 978-0-387-96254-2. ↩

  13. "One of the most important unsolved problems in the theory of finite fields is designing a fast algorithm to construct primitive roots. von zur Gathen & Shparlinski 1998, pp. 15–24 - von zur Gathen, Joachim; Shparlinski, Igor (1998). "Orders of Gauss periods in finite fields". Applicable Algebra in Engineering, Communication and Computing. 9 (1): 15–24. CiteSeerX 10.1.1.46.5504. doi:10.1007/s002000050093. MR 1624824. S2CID 19232025. https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.46.5504 ↩

  14. "There is no convenient formula for computing [the least primitive root]." Robbins 2006, p. 159 - Robbins, Neville (2006). Beginning Number Theory. Jones & Bartlett Learning. ISBN 978-0-7637-3768-9. https://books.google.com/books?id=TtLMrKDsDuIC&pg=PA159 ↩

  15. (sequence A010554 in the OEIS) //oeis.org/A010554 ↩

  16. Knuth, Donald E. (1998). Seminumerical Algorithms. The Art of Computer Programming. Vol. 2 (3rd ed.). Addison–Wesley. section 4.5.4, page 391. ↩

  17. Cohen, Henri (1993). A Course in Computational Algebraic Number Theory. Berlin: Springer. p. 26. ISBN 978-3-540-55640-4. 978-3-540-55640-4 ↩

  18. Cohen, Henri (1993). A Course in Computational Algebraic Number Theory. Berlin: Springer. p. 26. ISBN 978-3-540-55640-4. 978-3-540-55640-4 ↩

  19. Ribenboim, Paulo (1996). The New Book of Prime Number Records. New York, NY: Springer. p. 24. ISBN 978-0-387-94457-9. 978-0-387-94457-9 ↩

  20. Burgess, D. A. (1962). "On Character Sums and Primitive Roots †". Proceedings of the London Mathematical Society. s3-12 (1): 179–192. doi:10.1112/plms/s3-12.1.179. http://doi.wiley.com/10.1112/plms/s3-12.1.179 ↩

  21. Ribenboim, Paulo (1996). The New Book of Prime Number Records. New York, NY: Springer. p. 24. ISBN 978-0-387-94457-9. 978-0-387-94457-9 ↩

  22. Grosswald, E. (1981). "On Burgess' Bound for Primitive Roots Modulo Primes and an Application to Γ(p)". American Journal of Mathematics. 103 (6): 1171–1183. doi:10.2307/2374229. ISSN 0002-9327. JSTOR 2374229. https://www.jstor.org/stable/2374229 ↩

  23. Bach & Shallit 1996, p. 254. - Bach, Eric; Shallit, Jeffrey (1996). Efficient Algorithms. Algorithmic Number Theory. Vol. I. Cambridge, MA: The MIT Press. ISBN 978-0-262-02405-1. ↩

  24. Ribenboim, Paulo (1996). The New Book of Prime Number Records. New York, NY: Springer. p. 24. ISBN 978-0-387-94457-9. 978-0-387-94457-9 ↩

  25. Ribenboim, Paulo (1996). The New Book of Prime Number Records. New York, NY: Springer. p. 24. ISBN 978-0-387-94457-9. 978-0-387-94457-9 ↩

  26. Gentle, James E. (2003). Random number generation and Monte Carlo methods (2nd ed.). New York: Springer. ISBN 0-387-00178-6. OCLC 51534945. 0-387-00178-6 ↩

  27. Walker, R. (1990). The design and application of modular acoustic diffusing elements (PDF). BBC Research Department (Report). British Broadcasting Corporation. Retrieved 25 March 2019. http://downloads.bbc.co.uk/rd/pubs/reports/1990-15.pdf ↩

  28. Feldman, Eliot (July 1995). "A reflection grating that nullifies the specular reflection: A cone of silence". J. Acoust. Soc. Am. 98 (1): 623–634. Bibcode:1995ASAJ...98..623F. doi:10.1121/1.413656. /wiki/Bibcode_(identifier) ↩