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:
“The order of the world is always right—such is the judgment of God. For God has departed, but he has left his judgment behind, the way the Cheshire Cat left his grin.”
—Jean Baudrillard (b. 1929)
“Life has no meaning unless one lives it with a will, at least to the limit of one’s will. Virtue, good, evil are nothing but words, unless one takes them apart in order to build something with them; they do not win their true meaning until one knows how to apply them.”
—Paul Gauguin (1848–1903)
“Government is either organized benevolence or organized madness; its peculiar magnitude permits no shading.”
—John Updike (b. 1932)
“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)
““Jim,” she said earnestly, “if I was put down there in the middle of the night, I could find my way all over that little town; and along the river to the next town, where my grandmother lived. My feet remember all the little paths through the woods, and where the big roots stick out to trip you. I ain’t never forgot my own country.””
—Willa Cather (1873–1947)