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:
“Just as a new scientific discovery manifests something that was already latent in the order of nature, and at the same time is logically related to the total structure of the existing science, so the new poem manifests something that was already latent in the order of words.”
—Northrop Frye (b. 1912)
“We enter parliament in order to supply ourselves, in the arsenal of democracy, with its own weapons.... If democracy is so stupid as to give us free tickets and salaries for this bear’s work, that is its affair.... We do not come as friends, nor even as neutrals. We come as enemies. As the wolf bursts into the flock, so we come.”
—Joseph Goebbels (1897–1945)
“Sometimes you’re overwhelmed when a thing comes, and you do not realize the magnitude of the affair at that moment. When you get away from it, you wonder, did it really happen to you.”
—Marian Anderson (1902–1993)
“The mountainous region of the State of Maine stretches from near the White Mountains, northeasterly one hundred and sixty miles, to the head of the Aroostook River, and is about sixty miles wide. The wild or unsettled portion is far more extensive. So that some hours only of travel in this direction will carry the curious to the verge of a primitive forest, more interesting, perhaps, on all accounts, than they would reach by going a thousand miles westward.”
—Henry David Thoreau (1817–1862)
“There is nothing but is related to us, nothing that does not interest us,—kingdom, college, tree, horse, or iron show,—the roots of all things are in man.”
—Ralph Waldo Emerson (1803–1882)