Order of Magnitude of Primitive Roots
The least primitive root modulo p is generally small.
Let gp be the smallest primitive root modulo p in the range 1, 2, ..., p–1.
Fridlander (1949) and Salié (1950) proved that there is a positive constant C such that for infinitely many primes gp > 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 < gp < p – M.
Burgess (1962) proved that for every ε > 0 there is a C such that
Grosswald (1981) proved that if, then .
Shoup (1990, 1992) proved, assuming the generalized Riemann hypothesis, that gp =O(log6 p).
Read more about this topic: Primitive Root Modulo n
Famous quotes containing the words order, magnitude, primitive and/or roots:
“I tell you, sir, the only safeguard of order and discipline in the modern world is a standardized worker with interchangeable parts. That would solve the entire problem of management.”
—Jean Giraudoux (1882–1944)
“Although a man may lose a sense of his own importance when he is a mere unit among a busy throng, all utterly regardless of him, it by no means follows that he can dispossess himself, with equal facility, of a very strong sense of the importance and magnitude of his cares.”
—Charles Dickens (1812–1870)
“This is a very primitive country.”
—James Poe (1921–1980)
“He who sins easily, sins less. The very power
Renders less vigorous the roots of evil.”
—Ovid (Publius Ovidius Naso)