Editing Primitive root modulo n (section)

==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}}.}}