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:
“The confusion of emotions with behavior causes no end of unnecessary trouble to both adults and children. Behavior can be commanded; emotions can’t. An adult can put controls on a child’s behavior—at least part of the time—but how do you put controls on what a child feels? An adult can impose controls on his own behavior—if he’s grown up—but how does he order what he feels?”
—Leontine Young (20th century)
“He all their ammunition
And feats of war defeats
With plain heroic magnitude of mind
And celestial vigour armed;”
—John Milton (1608–1674)
“Not only do our wives need support, but our children need our deep involvement in their lives. If this period [the early years] of primitive needs and primitive caretaking passes without us, it is lost forever. We can be involved in other ways, but never again on this profoundly intimate level.”
—Augustus Y. Napier (20th century)
“Sprung from the West,
He drank the valorous youth of a new world.
The strength of virgin forests braced his mind,
The hush of spacious prairies stilled his soul.
His words were oaks in acorns; and his thoughts
Were roots that firmly gript the granite truth.”
—Edwin Markham (1852–1940)