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:
“Humility is often merely feigned submissiveness assumed in order to subject others, an artifice of pride which stoops to conquer, and although pride has a thousand ways of transforming itself it is never so well disguised and able to take people in as when masquerading as humility.”
—François, Duc De La Rochefoucauld (1613–1680)
“We quaff the cup of life with eager haste without draining it, instead of which it only overflows the brim—objects press around us, filling the mind with their magnitude and with the throng of desires that wait upon them, so that we have no room for the thoughts of death.”
—William Hazlitt (1778–1830)
“Through the din and desultoriness of noon, even in the most Oriental city, is seen the fresh and primitive and savage nature, in which Scythians and Ethiopians and Indians dwell. What is echo, what are light and shade, day and night, ocean and stars, earthquake and eclipse, there? The works of man are everywhere swallowed up in the immensity of nature. The AEgean Sea is but Lake Huron still to the Indian.”
—Henry David Thoreau (1817–1862)
“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)