Editing Primitive root modulo n

{{Short description|Modular arithmetic concept}}
{{DISPLAYTITLE:Primitive root modulo {{mvar|n}}}}
In [[modular arithmetic]], a number {{mvar|g}} is a '''primitive root modulo&nbsp;{{mvar|n}}''' if every number {{mvar|a}} [[coprime]] to {{mvar|n}} is [[Congruence relation|congruent]] to a power of {{mvar|g}} modulo {{mvar|n}}. That is, {{mvar|g}} is a ''primitive root modulo''&nbsp;{{mvar|n}} if for every integer {{mvar|a}} coprime to {{mvar|n}}, there is some integer {{mvar|k}} for which {{mvar|g}}<sup>{{mvar|k}}</sup> ≡ {{mvar|a}} (mod&nbsp;{{mvar|n}}). Such a value {{mvar|k}} is called the '''index''' or '''[[discrete logarithm]]''' of {{mvar|a}} to the base {{mvar|g}} modulo {{mvar|n}}. So {{mvar|g}} is a ''primitive root modulo''&nbsp;{{mvar|n}} if and only if {{mvar|g}} is a [[Generating_set_of_a_group|generator]] of the [[multiplicative group of integers modulo n|multiplicative group of integers modulo {{mvar|n}}]].

[[Carl Friedrich Gauss|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 [[Johann Heinrich Lambert|Lambert]] and Euler knew of them, but he was the first to rigorously demonstrate that primitive roots exist for a [[Prime number|prime]] {{mvar|n}}. In fact, the ''Disquisitiones'' contains two proofs: The one in Article 54 is a nonconstructive [[Existence theorem|existence proof]], while the proof in Article 55 is [[Constructive proof|constructive]].

A primitive root exists if and only if ''n'' is 1, 2, 4, ''p''<sup>''k''</sup> or 2''p''<sup>''k''</sup>, where ''p'' is an odd prime and {{nowrap|''k'' > 0}}. For all other values of ''n'' the multiplicative group of integers modulo ''n'' is not [[cyclic group|cyclic]].<ref>{{MathWorld|title=Modulo Multiplication Group|urlname=ModuloMultiplicationGroup}}
</ref><ref name=":0">{{Cite web |title=Primitive root - Encyclopedia of Mathematics |url=https://encyclopediaofmath.org:443/wiki/Primitive_root |access-date=2024-11-05 |website=encyclopediaofmath.org}}</ref><ref name="Vinogradov2003.pp=105-121">{{Harv|Vinogradov|2003|loc=§ VI PRIMITIVE ROOTS AND INDICES|pp=105–121}}</ref>
This was first proved by [[Carl Friedrich Gauss|Gauss]].<ref>{{Harv|Gauss|1986|loc=arts. 52–56, 82–891}}</ref>

==Elementary example==
The number 3 is a primitive root modulo&nbsp;7<ref>{{cite web |last=Stromquist |first=Walter |title=What are primitive roots? |publisher=Bryn Mawr College |department=Mathematics |url=http://www.brynmawr.edu/math/people/stromquist/numbers/primitive.html |access-date=2017-07-03 |url-status=dead |archive-url=https://web.archive.org/web/20170703173446/http://www.brynmawr.edu/math/people/stromquist/numbers/primitive.html |archive-date=2017-07-03}}</ref> because
<math display="block">
\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}
</math>

Here we see that the [[order (group theory)|period]] of 3<sup>{{mvar|k}}</sup> modulo&nbsp;7 is 6. The remainders in the period, which are 3, 2, 6, 4, 5, 1, form a rearrangement of all nonzero remainders modulo&nbsp;7, implying that 3 is indeed a primitive root modulo&nbsp;7. This derives from the fact that a sequence ({{mvar|g}}<sup>{{mvar|k}}</sup> modulo&nbsp;{{mvar|n}}) always repeats after some value of {{mvar|k}}, since modulo&nbsp;{{mvar|n}} produces a finite number of values. If {{mvar|g}} is a primitive root modulo&nbsp;{{mvar|n}} and {{mvar|n}} is prime, then the period of repetition is {{nowrap|{{mvar|n}} − 1.}} Permutations created in this way (and their circular shifts) have been shown to be [[Costas array#Welch|Costas arrays]].

==Definition==
If {{mvar|n}} is a positive integer, the integers from 1 to {{nowrap|{{mvar|n}} − 1}} that are [[coprime]] to {{mvar|n}} (or equivalently, the [[congruence class]]es coprime to {{mvar|n}}) form a [[group (mathematics)|group]], with multiplication [[Modular arithmetic|modulo]] {{mvar|n}} as the operation; it is denoted by [[multiplicative group of integers modulo n|<math>\mathbb{Z}</math>{{su|b={{mvar|n}}|p=×}}]], and is called the [[group of units]] modulo {{mvar|n}}, or the group of primitive classes modulo {{mvar|n}}. As explained in the article [[multiplicative group of integers modulo n|multiplicative group of integers modulo {{mvar|n}}]], this multiplicative group (<math>\mathbb{Z}</math>{{su|b={{mvar|n}}|p=×}}) is [[cyclic group|cyclic]] '''if and only if''' {{mvar|n}} is equal to 2, 4, {{mvar|p{{sup|k}}}}, or 2{{mvar|p{{sup|k}}}} where {{mvar|p{{sup|k}}}} is a power of an odd [[prime number]].<ref>{{MathWorld |title=Modulo Multiplication Group |urlname=ModuloMultiplicationGroup}}
</ref><ref name=":0" /><ref name="Vinogradov2003.pp=105–121">{{Harvnb|Vinogradov|2003|loc=§ VI Primitive roots and indices|pp=105–121}}.</ref> When (and only when) this group <math>\mathbb{Z}</math>{{su|b={{mvar|n}}|p=×}} is cyclic, a [[generating set of a group|generator]] of this cyclic group is called a '''primitive root modulo {{mvar|n}}'''<ref>{{Harvnb|Vinogradov|2003|p=106}}.</ref> (or in fuller language '''primitive root of unity modulo {{mvar|n}}''', emphasizing its role as a fundamental solution of the '''[[Root of unity modulo n|roots of unity]]''' polynomial equations X{{su|p={{mvar|m}}}} − 1 in the ring <math>\mathbb{Z}</math>{{sub|{{mvar|n}}}}), or simply a '''primitive element of''' <math>\mathbb{Z}</math>{{su|b={{mvar|n}}|p=×}}.

When <math>\mathbb{Z}</math>{{su|b={{mvar|n}}|p=×}} is non-cyclic, such primitive elements mod {{mvar|n}} do not exist. Instead, each prime component of {{mvar|n}} has its own sub-primitive roots (see {{math|15}} in the examples below).

For any {{mvar|n}} (whether or not <math>\mathbb{Z}</math>{{su|b={{mvar|n}}|p=×}} is cyclic), the order of <math>\mathbb{Z}</math>{{su|b={{mvar|n}}|p=×}} is given by [[Euler's totient function]] {{mvar|φ}}({{mvar|n}}) {{OEIS|id=A000010}}. And then, [[Euler's theorem]] says that {{nowrap|{{mvar|a}}<sup>{{mvar|φ}}({{mvar|n}})</sup> ≡ 1 (mod {{mvar|n}})}} for every {{mvar|a}} coprime to {{mvar|n}}; the lowest power of {{mvar|a}} that is congruent to 1 modulo {{mvar|n}} is called the [[multiplicative order]] of {{mvar|a}} modulo {{mvar|n}}. In particular, for {{mvar|a}} to be a primitive root modulo {{mvar|n}}, {{nowrap|{{mvar|a}}<sup>{{mvar|φ}}({{mvar|n}})</sup> }} has to be the smallest power of {{mvar|a}} that is congruent to 1 modulo {{mvar|n}}.

==Examples==

For example, if {{nowrap|{{mvar|n}} {{=}} 14}} then the elements of <math>\mathbb{Z}</math>{{su|b={{mvar|n}}|p=×}} are the congruence classes {1, 3, 5, 9, 11, 13}; there are {{nowrap|{{mvar|φ}}(14) {{=}} 6}} of them. Here is a table of their powers modulo 14:

  x     x, x<sup>2</sup>, x<sup>3</sup>, ... (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 {{nowrap|{{mvar|n}} {{=}} 15 .}} The elements of <math>\mathbb{Z}</math>{{su|b=15|p=×}} are the congruence classes {1, 2, 4, 7, 8, 11, 13, 14}; there are {{nowrap|{{mvar|φ}}(15) {{=}} 8}} of them.

  x     x, x<sup>2</sup>, x<sup>3</sup>, ... (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, {{nowrap|{{mvar|λ}}(15) {{=}} 4}}, where {{mvar|λ}} is the [[Carmichael function]]. {{OEIS|id=A002322}}

==Table of primitive roots==

Numbers <math>n</math> that have a primitive root are of the shape
:<math>n \in \{1, 2, 4, p^k, 2 \cdot p^k \; \; | \; \; 2 < p \text{ prime}; \; k \in \mathbb{N}\} ,</math>
:= {1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 17, 18, 19, ...}.<ref>{{Harvnb|Gauss|1986|loc=art 92}}.</ref>
These are the numbers <math>n</math> with <math>\varphi(n) = \lambda(n),</math> kept also in the sequence {{OEIS link|id=A033948}} in the [[OEIS]].

The following table lists the primitive roots modulo {{mvar|n}} up to <math>n=31</math>:
{|class="wikitable"
!{{tmath|n}}
!primitive roots modulo {{tmath|n}}
!order <math>\varphi(n),</math><br />({{oeis|id=A000010}})
![[Torsion group|exponent]] <math>\lambda(n),</math><br />({{oeis|id=A002322}})
|-
|1||0||1||1
|-
|2||1||1||1
|-
|3||2||2||2
|-
|4||3||2||2
|-
|5||2, 3||4||4
|-
|6||5||2||2
|-
|7||3, 5||6||6
|-
|8|| ||4||2
|-
|9||2, 5||6||6
|-
||10||3, 7||4||4
|-
||11||2, 6, 7, 8||10||10
|-
||12|| ||4||2
|-
||13||2, 6, 7, 11||12||12
|-
||14||3, 5||6||6
|-
||15|| ||8||4
|-
||16|| ||8||4
|-
||17||3, 5, 6, 7, 10, 11, 12, 14||16||16
|-
||18||5, 11||6||6
|-
||19||2, 3, 10, 13, 14, 15||18||18
|-
||20|| ||8||4
|-
||21|| ||12||6
|-
||22||7, 13, 17, 19||10||10
|-
||23||5, 7, 10, 11, 14, 15, 17, 19, 20, 21||22||22
|-
||24|| ||8||2
|-
||25||2, 3, 8, 12, 13, 17, 22, 23||20||20
|-
||26||7, 11, 15, 19||12||12
|-
||27||2, 5, 11, 14, 20, 23||18||18
|-
||28|| ||12||6
|-
||29||2, 3, 8, 10, 11, 14, 15, 18, 19, 21, 26, 27||28||28
|-
||30|| ||8||4
|-
||31||3, 11, 12, 13, 17, 21, 22, 24||30||30
|}

==Properties==

Gauss proved<ref>{{Harvnb|Gauss|1986|loc=arts. 80}}.</ref> that for any prime number {{mvar|p}} (with the sole exception of {{nowrap|{{mvar|p}} {{=}} 3),}} the product of its primitive roots is congruent to 1 modulo {{mvar|p}}.

He also proved<ref>{{Harvnb|Gauss|1986|loc=art 81}}.</ref> that for any prime number {{mvar|p}}, the sum of its primitive roots is congruent to {{mvar|μ}}({{mvar|p}} − 1) modulo {{mvar|p}}, where {{mvar|μ}} is the [[Möbius function]].

For example,
:{|
|-
|{{mvar|p}} = 3, || {{mvar|μ}}(2) = −1. || The primitive root is 2.
|-
|{{mvar|p}} = 5, || {{mvar|μ}}(4) = 0. || The primitive roots are 2 and 3.
|-
|{{mvar|p}} = 7, || {{mvar|μ}}(6) = 1. || The primitive roots are 3 and 5.
|-
|{{mvar|p}} = 31, ||{{mvar|μ}}(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 <math>2^6\cdot 3^4\cdot 7\cdot 11^2\cdot 13\cdot 17 = 970377408 \equiv 1 \pmod{31}</math>, and their sum is <math>123 \equiv -1 \equiv \mu(31-1) \pmod{31}</math>.

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

[[Artin's conjecture on primitive roots]] states that a given integer {{mvar|a}} that is neither a [[Square number|perfect square]] nor &minus;1 is a primitive root modulo infinitely many [[prime number|primes]].

==Finding primitive roots==

No simple general formula to compute primitive roots modulo {{mvar|n}} is known.{{efn|"One of the most important unsolved problems in the theory of finite fields is designing a fast algorithm to construct primitive roots. {{Harvnb|von zur Gathen|Shparlinski|1998|pp=15–24}} }}{{efn|"There is no convenient formula for computing [the least primitive root]." {{Harvnb|Robbins|2006|p=159}} }} There are however methods to locate a primitive root that are faster than simply trying out all candidates. If the [[multiplicative order]] (its [[Torsion group|exponent]]) of a number {{mvar|m}} modulo {{mvar|n}} is equal to [[Euler's phi function|<math>\varphi(n)</math>]] (the order of <math>\mathbb{Z}</math>{{su|b={{mvar|n}}|p=×}}), then it is a primitive root. In fact the converse is true: If {{mvar|m}} is a primitive root modulo {{mvar|n}}, then the multiplicative order of {{mvar|m}} is <math>\varphi(n) = \lambda(n)~.</math> We can use this to test a candidate {{mvar|m}} to see if it is primitive.

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

The number of primitive roots modulo {{mvar|n}}, if there are any, is equal to<ref>{{OEIS|A010554}}</ref>
:<math>\varphi\left(\varphi(n)\right)</math>
since, in general, a cyclic group with {{mvar|r}} elements has <math>\varphi(r)</math> generators.

For prime {{mvar|n}}, this equals <math>\varphi(n-1)</math>, and since <math>n / \varphi(n-1) \in O(\log\log n)</math> the generators are very common among {2, ..., {{mvar|n}}&minus;1} and thus it is relatively easy to find one.<ref name=Knuth-1998/>

If {{mvar|g}} is a primitive root modulo {{mvar|p}}, then {{mvar|g}} is also a primitive root modulo all powers {{mvar|p{{sup|k}}}} unless {{mvar|g}}<sup>{{mvar|p}}−1</sup> ≡ 1 (mod {{mvar|p}}<sup>2</sup>); in that case, {{mvar|g}} + {{mvar|p}} is.<ref name="Cohen1993"/>

If {{mvar|g}} is a primitive root modulo {{mvar|p{{sup|k}}}}, then {{mvar|g}} is also a primitive root modulo all smaller powers of {{mvar|p}}.

If {{mvar|g}} is a primitive root modulo {{mvar|p{{sup|k}}}}, then either {{mvar|g}} or {{mvar|g}} + {{mvar|p{{sup|k}}}} (whichever one is odd) is a primitive root modulo 2{{mvar|p{{sup|k}}}}.<ref name="Cohen1993"/>

Finding primitive roots modulo {{mvar|p}} is also equivalent to finding the roots of the ({{mvar|p}} − 1)st [[cyclotomic polynomial]] modulo {{mvar|p}}.

==Order of magnitude of primitive roots==

The least primitive root {{mvar|g{{sub|p}}}} modulo {{mvar|p}} (in the range 1, 2, ..., {{nowrap|{{mvar|p}} − 1)}} is generally small.

===Upper bounds===
Burgess (1962) proved<ref name="Ribenboim, p.24"/><ref>{{Cite journal |last=Burgess |first=D. A. |date=1962 |title=On Character Sums and Primitive Roots † |url=http://doi.wiley.com/10.1112/plms/s3-12.1.179 |journal=[[Proceedings of the London Mathematical Society]] |language=en |volume=s3-12 |issue=1 |pages=179–192 |doi=10.1112/plms/s3-12.1.179}}</ref> that for every ''ε'' > 0 there is a {{mvar|C}} such that <math>g_p \leq C\,p^{\frac{1}{4}+\varepsilon}.</math>

[[Emil Grosswald|Grosswald]] (1981) proved<ref name="Ribenboim, p.24"/><ref>{{Cite journal |last=Grosswald |first=E. |date=1981 |title=On Burgess' Bound for Primitive Roots Modulo Primes and an Application to Γ(p) |url=https://www.jstor.org/stable/2374229 |journal=[[American Journal of Mathematics]] |volume=103 |issue=6 |pages=1171–1183 |doi=10.2307/2374229 |jstor=2374229 |issn=0002-9327}}</ref> that if <math>p > e^{e^{24}} \approx 10^{11504079571}</math>, then <math>g_p < p^{0.499}.</math>

[[Victor Shoup|Shoup]] (1990, 1992) proved,<ref>{{Harvnb|Bach|Shallit|1996|p=254}}.</ref> assuming the [[generalized Riemann hypothesis]], that {{nowrap|{{mvar|g{{sub|p}}}} {{=}} O(log<sup>6</sup> {{mvar|p}}).}}

===Lower bounds===
Fridlander (1949) and Salié (1950) proved<ref name="Ribenboim, p.24"/> that there is a positive constant {{mvar|C}} such that for infinitely many primes {{nowrap|{{mvar|g{{sub|p}}}} > {{mvar|C}} log {{mvar|p}}.}}

It can be proved<ref name="Ribenboim, p.24"/> in an elementary manner that for any positive integer {{mvar|M}} there are infinitely many primes such that {{mvar|M}} < {{mvar|g{{sub|p}}}} < {{nowrap|{{mvar|p}} − {{mvar|M}}.}}

== Applications ==

A primitive root modulo {{mvar|n}} is often used in [[Pseudorandom number generator|pseudorandom number generators]]<ref>{{Cite book |last=Gentle |first=James E. |url=https://www.worldcat.org/oclc/51534945 |title=Random number generation and Monte Carlo methods |date=2003 |publisher=Springer |isbn=0-387-00178-6 |edition=2nd |location=New York |oclc=51534945}}</ref> and [[cryptography]], including the [[Diffie–Hellman key exchange]] scheme. [[Diffusion (acoustics)#Primitive-root diffusors|Sound diffusers]] have been based on number-theoretic concepts such as primitive roots and [[Quadratic residue|quadratic residues]].<ref name=Walker-1990/><ref name=Feldman/>

==See also==
{{Div col}}
* [[Dirichlet character]]
* [[Full reptend prime]]
* [[Wilson's theorem#Gauss.27s generalization|Gauss's generalization of Wilson's theorem]]
* [[Multiplicative order]]
* [[Quadratic residue]]
* [[Root of unity modulo n|Root of unity modulo {{mvar|n}}]]
* [[Artin's conjecture on primitive roots]]
{{Div col end}}

==Footnotes==
{{notelist|1}}

==References==
{{reflist|refs=
<!--<ref name="Carella-2015">{{cite journal|title=Least Prime Primitive Roots|last1=Carella|first1=N.A.|year=2015|journal=International Journal of Mathematics and Computer Science|volume=10|issue=2|pages=185–194|arxiv=1709.01172}}</ref>-->

<ref name="Cohen1993">{{cite book | last1 = Cohen | first1 = Henri | author-link = Henri Cohen (number theorist) | year = 1993 | title = A Course in Computational Algebraic Number Theory | page = 26 | publisher = [[Springer Science+Business Media|Springer]] | location = Berlin | isbn = 978-3-540-55640-4}}</ref>

<ref name="Feldman">{{cite journal |first = Eliot |last = Feldman |date = July 1995 |title = A reflection grating that nullifies the specular reflection: A cone of silence |journal = J. Acoust. Soc. Am. |volume = 98 |issue = 1 |pages = 623–634 |doi = 10.1121/1.413656 |bibcode = 1995ASAJ...98..623F}}</ref>

<ref name="Knuth-1998">{{cite book | first = Donald E. | last = Knuth | year = 1998 | title = Seminumerical Algorithms | edition = 3rd | at = section&nbsp;4.5.4, page&nbsp;391 | series = The Art of Computer Programming | volume= 2 | publisher = Addison–Wesley}}</ref>

<ref name="Ribenboim, p.24">{{cite book | last = Ribenboim | first = Paulo | author-link = Paulo Ribenboim | year = 1996 | title = The New Book of Prime Number Records | page = 24 | publisher = [[Springer Science+Business Media|Springer]] | location = New York, NY | isbn = 978-0-387-94457-9}}</ref>

<ref name="Walker-1990">{{cite report |last=Walker |first=R. |year=1990 |title=The design and application of modular acoustic diffusing elements |url=http://downloads.bbc.co.uk/rd/pubs/reports/1990-15.pdf |department=BBC Research Department |publisher=[[British Broadcasting Corporation]] |access-date=25 March 2019}}</ref>
}}

==Sources==
{{refbegin}}

* {{cite book
 | last1 = Bach     | first1 = Eric
 | last2 = Shallit  | first2 = Jeffrey
 | year = 1996
 | title = Efficient Algorithms
 | series = Algorithmic Number Theory  | volume = I
 | publisher = [[The MIT Press]]
 | location = Cambridge, MA
 | isbn = 978-0-262-02405-1
}}

* {{cite journal
 | last1 = Carella  | first1 = N. A.
 | year = 2015
 | title = Least Prime Primitive Roots
 | journal = International Journal of Mathematics and Computer Science
 | volume = 10  | issue = 2  | pages = 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.

*{{cite book
 | last = Gauss | first = Carl Friedrich | author-link = Carl Friedrich Gauss
 | translator-last = Clarke  | translator-first = Arthur A.
 | orig-year = 1801  | year = 1986
 | title = Disquisitiones Arithmeticae   | edition = 2nd, corrected
 | publisher = [[Springer Science+Business Media|Springer]]
 | location = New York, NY
 | isbn = 978-0-387-96254-2
 | lang = EN
}}

*{{cite book
 | last = Gauss | first = Carl Friedrich | author-link = Carl Friedrich Gauss
 | translator-last = Maser  | translator-first = H.
 | orig-year = 1801  | year = 1965
 | title = Untersuchungen über höhere Arithmetik   | edition = 2nd
 | trans-title = Studies of Higher Arithmetic
 | publisher = Chelsea
 | location = New York, NY
 | isbn = 978-0-8284-0191-3
 | lang = DE
}}

*{{cite book
 | first = Neville  | last = Robbins
 | year = 2006
 | title = Beginning Number Theory
 | publisher = Jones & Bartlett Learning
 | isbn = 978-0-7637-3768-9
 | url = https://books.google.com/books?id=TtLMrKDsDuIC&pg=PA159
}}

*{{cite book
 | last = Vinogradov  | first = I.M.
 | author-link = Ivan Matveyevich Vinogradov
 | year = 2003
 | title = Elements of Number Theory
 | chapter = §&nbsp;VI Primitive roots and indices
 | pages = 105–121
 | publisher = Dover Publications
 | location = Mineola, NY
 | isbn = 978-0-486-49530-9
 | chapter-url = https://books.google.com/books?id=xlIfdGPM9t4C&pg=PA105
}}

*{{cite journal
 | last1 = von zur Gathen  | first1 = Joachim
 | author1-link = Joachim von zur Gathen
 | last2 = Shparlinski  | first2 = Igor
 | year = 1998
 | title = Orders of Gauss periods in finite fields
 | journal = Applicable Algebra in Engineering, Communication and Computing
 | volume = 9  | issue = 1  | pages = 15–24
 | mr = 1624824  | citeseerx = 10.1.1.46.5504  | s2cid = 19232025
 | doi = 10.1007/s002000050093
 }}
{{refend}}

==Further reading==
*{{cite book
 | last = Ore  | first = Oystein  | author-link = Øystein Ore
 | year = 1988
 | title = Number Theory and Its History
 | publisher = Dover
 | pages = [https://archive.org/details/numbertheoryitsh0000orey/page/284 284–302]
 | isbn = 978-0-486-65620-5
 | url = https://archive.org/details/numbertheoryitsh0000orey/page/284
 }}.

==External links==
* {{MathWorld
 | title = Primitive Root
 | id = PrimitiveRoot
}}
*{{cite web
 | last = Holt
 | title = Quadratic residues and primitive roots
 | publisher = Michigan Tech
 | department = Mathematics
 | url = http://www.math.mtu.edu/mathlab/COURSES/holt/dnt/quadratic4.html
}}
* {{cite web
 | title = Primitive roots calculator
 | website = BlueTulip
 | url = http://www.bluetulip.org/programs/primitive.html
}}

[[Category:Modular arithmetic]]