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 of, order, magnitude, primitive and/or roots:
“It is the international system of currency which determines the totality of life on this planet. That is the natural order of things today. That is the atomic, and sub-atomic, and galactic
structure of things today. And you have meddled with the primal forces of nature! And you will atone! Am I getting through to you, Mr. Beale?”
—Paddy Chayefsky (1923–1981)
“In order for the artist to have a world to express he must first be situated in this world, oppressed or oppressing, resigned or rebellious, a man among men.”
—Simone De Beauvoir (1908–1986)
“He all their ammunition
And feats of war defeats
With plain heroic magnitude of mind
And celestial vigour armed;”
—John Milton (1608–1674)
“Cannibalism to a certain moderate extent is practised among several of the primitive tribes in the Pacific, but it is upon the bodies of slain enemies alone; and horrible and fearful as the custom is, immeasurably as it is to be abhorred and condemned, still I assert that those who indulge in it are in other respects humane and virtuous.”
—Herman Melville (1819–1891)
“Einstein is not ... merely an artist in his moments of leisure and play, as a great statesman may play golf or a great soldier grow orchids. He retains the same attitude in the whole of his work. He traces science to its roots in emotion, which is exactly where art is also rooted.”
—Havelock Ellis (1859–1939)