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:
“A sleeping man holds in a circle around him the thread of the hours, the order of years and of worlds. He consults them instinctively upon awaking and in one second reads in them the point of the earth that he occupies, the time past until his arousal; but their ranks can be mingled or broken.”
—Marcel Proust (1871–1922)
“In a secular age, an authentic miracle must purport to be a hoax, in order to gain credit in the world.”
—Angela Carter (1940–1992)
“Government is either organized benevolence or organized madness; its peculiar magnitude permits no shading.”
—John Updike (b. 1932)
“Financiers are great mythomaniacs, their explanations and superstitions are those of primitive men; the world is a jungle to them. They perceive acutely that they are at the dawn of economic history.”
—Christina Stead (1902–1983)
“Now fades the lasts long streak of snow,
Now burgeons every maze of quick
About the flowering squares, and thick
By ashen roots the violets blow.”
—Alfred Tennyson (1809–1892)