View source for Primitive root modulo n

{{Short description|Modular arithmetic concept}}
{{DISPLAYTITLE:Primitive root modulo {{mvar|n}}}}
In [[Modular arithmetic|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|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}}]].

[[Biography: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 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>[http://www.encyclopediaofmath.org/index.php/Primitive_root Primitive root], [[Encyclopedia of Mathematics]]</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 [[Biography:Carl Friedrich Gauss|Gauss]].<ref>{{Harv|Gauss|Clarke|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 classes 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|prime number]].<ref>{{MathWorld |title=Modulo Multiplication Group |urlname=ModuloMultiplicationGroup}}
</ref><ref>[http://www.encyclopediaofmath.org/index.php/Primitive_root Primitive root], [[Encyclopedia of Mathematics]].</ref><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|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|Clarke|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|Clarke|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|Clarke|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|multiplicative order]] (its [[Torsion group|exponent]]) of a number {{mvar|m}} modulo {{mvar|n}} is equal to <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 factors 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|modular exponentiation]] such as [[Exponentiation by squaring|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|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=[[Organization:Proceedings of the London Mathematical Society|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>

[[Biography: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>

[[Biography:Victor Shoup|Shoup]] (1990, 1992) proved,<ref>{{Harvnb|Bach|Shallit|1996|p=254}}.</ref> assuming the [[Generalized Riemann hypothesis|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|cryptography]], including the [[Diffie–Hellman key exchange]] scheme. [[Physics: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}}]]
{{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 |  year = 1993 | title = A Course in Computational Algebraic Number Theory | page = 26 | publisher = [[Company: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 |  year = 1996 | title = The New Book of Prime Number Records | page = 24 | publisher = [[Company: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
 | translator-last = Clarke  | translator-first = Arthur A.
 | orig-year = 1801  | year = 1986
 | title = Disquisitiones Arithmeticae   | edition = 2nd, corrected
 | publisher = [[Company:Springer Science+Business Media|Springer]]
 | location = New York, NY
 | isbn = 978-0-387-96254-2
 | lang = EN
}}

*{{cite book
 | 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.
 | 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
 | 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
 | 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]]

{{Sourceattribution|Primitive root modulo n}}