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:
“Judicial judgment must take deep account ... of the day before yesterday in order that yesterday may not paralyze today.”
—Felix Frankfurter (1882–1965)
“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)
“In some ways being a parent is like being an anthropologist who is studying a primitive and isolated tribe by living with them.... To understand the beauty of child development, we must shed some of our socialization as adults and learn how to communicate with children on their own terms, just as an anthropologist must learn how to communicate with that primitive tribe.”
—Lawrence Kutner (20th century)
“The roots of the grass strain,
Tighten, the earth is rigid, waits—he is waiting—
And suddenly, and all at once, the rain!”
—Archibald MacLeish (1892–1982)