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 well within the order of things
That man should listen when his mate sings;
But the true male never yet walked
Who liked to listen when his mate talked.”
—Anna Wickham (1884–1947)
“Almost everywhere we find . . . the use of various coercive measures, to rid ourselves as quickly as possible of the child within us—i.e., the weak, helpless, dependent creature—in order to become an independent competent adult deserving of respect. When we reencounter this creature in our children, we persecute it with the same measures once used in ourselves.”
—Alice Miller (20th century)
“He all their ammunition
And feats of war defeats
With plain heroic magnitude of mind
And celestial vigour armed;”
—John Milton (1608–1674)
“[How] the young . . . can grow from the primitive to the civilized, from emotional anarchy to the disciplined freedom of maturity without losing the joy of spontaneity and the peace of self-honesty is a problem of education that no school and no culture have ever solved.”
—Leontine Young (20th century)
“The greatest gifts you can give your children are the roots of responsibility and the wings of independence.”
—Denis Waitly. Quoted in The Winning Family, ch. 25, by Louise Hart (1987)