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:
“Man is clearly made to think. It is his whole dignity and his whole merit; and his whole duty is to think as he ought. And the order of thought is to begin with ourselves, and with our Author and our end.”
—Blaise Pascal (1623–1662)
“Thoroughly to unfold the labyrinths of the human mind is an arduous task.... In order to dive into those recesses and lay them open to the reader in a striking and intelligible manner, ‘tis necessary to assume a certain freedom in writing, not strictly perhaps within the limits prescribed by rules.”
—Sarah Fielding (1710–1768)
“My time has come.
There are twenty people in my belly,
there is a magnitude of wings,
there are forty eyes shooting like arrows,
and they will all be born.
All be born in the yellow wind.”
—Anne Sexton (1928–1974)
“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)
“A good word is as a good tree—
its roots are firm,
and its branches are in heaven;
it gives its produce every season
by the leave of its Lord.”
—Qur’An. Abraham 14:29-30, ed. Arthur J. Arberry (1955)