Download Wolfram Notebook

A primitive root of a prime is an integer such that (mod ) has multiplicative order (Ribenboim 1996, p. 22). More generally, for an integer , if ( and are relatively prime) and is of multiplicative order modulo where is the totient function, then is a primitive root of (Burton 1989, p. 187). The first definition is a special case of the second since for a prime.

A primitive root of a number (but not necessarily the smallest primitive root for composite ) can be computed in the Wolfram Language using PrimitiveRoot[n].

If has a primitive root, then it has exactly incongruent primitive roots (Burton 1989, p. 188), which means that if is a prime number, then there are exactly incongruent primitive roots of (Burton 1989). For , 2, ..., the first few values of are 1, 1, 1, 1, 2, 1, 2, 2, 2, 2, 4, 2, 4, 2, 4, 4, 8, ... (OEIS A010554). An integer has a primitive root iff it is of the form 2, 4, , or , where is an odd prime and is a positive integer (Burton 1989, p. 204). The first few such are 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 17, 18, 19, 22, ... (OEIS A033948, with the initial 1 omitted). For , 3, ..., the numbers of primitive roots modulo are 1, 1, 1, 2, 1, 2, 0, 2, 2, 4, 0, 4, ... (OEIS A046144). These two OEIS sequences include a primitive root modulo 1, whereas the convention here restricts primitive roots to moduli .

The smallest primitive roots for the first few primes are 1, 2, 2, 3, 2, 2, 3, 2, 5, 2, 3, 2, 6, 3, 5, 2, 2, 2, ... (OEIS A001918). Here is a table of the primitive roots for the first few for which a primitive root exists (OEIS A046147).

The largest primitive roots among the integers 1, 2, ..., , or 0 when none exist, for , 2, ..., are 0, 1, 2, 3, 3, 5, 5, 0, 5, 7, 8, 0, 11, ... (OEIS A046146). The smallest primitive roots for the first few integers are given in the following table (OEIS A046145), which omits when does not exist.

Let be any odd prime, let be a positive integer, and let

Then

(Ribenboim 1996, pp. 22-23). For numbers with primitive roots, all satisfying are representable as

where is a primitive root of , , 1, ..., is known as the index, and is an integer. Let denote the least primitive root of a prime . Kearnes (1984) showed that for any positive integer , there exist infinitely many primes such that

Burgess (1962) proved that for every there is a positive constant such that

for sufficiently large (Ribenboim 1996, p. 24).

Vinogradov's least primitive root conjecture asks for the stronger estimate for every . A uniform version of the quasi-Riemann hypothesis would imply a power-of-logarithm bound for (Martin 1997, p. 278).

Matthews (1976) obtained a formula for the "two-dimensional" Artin's constants for the set of primes for which and are both primitive roots.

See also

Artin's Conjecture, Artin's Constant, Full Reptend Prime, Gaussian Period, Multiplicative Order, Primitive Element, Primitive Root of Unity, Vinogradov's Least Primitive Root Conjecture

Explore with Wolfram|Alpha

References

Abramowitz, M. and Stegun, I. A. (Eds.). "Primitive Roots." §24.3.4 in Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, 9th printing. New York: Dover, p. 827, 1972.Burgess, D. A. "On Character Sums and -Series." Proc. London Math. Soc. 12, 193-206, 1962.Burton, D. M. "The Order of an Integer Modulo ," "Primitive Roots for Primes," and "Composite Numbers Having Primitive Roots." §8.1-8.3 in Elementary Number Theory, 4th ed. Dubuque, IA: William C. Brown Publishers, pp. 184-205, 1989.Guy, R. K. "Primitive Roots." §F9 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 248-249, 1994.Jones, G. A. and Jones, J. M. "Primitive Roots." §6.2 in Elementary Number Theory. Berlin, Germany: Springer-Verlag, pp. 99-103, 1998.Kearnes, K. "Solution of Problem 6420." Amer. Math. Monthly 91, 521, 1984.Lehmer, D. H. "A Note on Primitive Roots." Scripta Math. 26, 117-119, 1961.Martin, G. "The Least Prime Primitive Root and the Shifted Sieve." Acta Arith. 80, 277-288, 1997. https://doi.org/10.4064/aa-80-3-277-288.Matthews, K. R. "A Generalization of Artin's Conjecture for Primitive Roots." Acta Arith. 29, 113-146, 1976.Nagell, T. "Moduli Having Primitive Roots." §32 in Introduction to Number Theory. New York: Wiley, pp. 107-111, 1951.Ribenboim, P. The New Book of Prime Number Records. New York: Springer-Verlag, pp. 22-25, 1996.Riesel, H. Prime Numbers and Computer Methods for Factorization, 2nd ed. Boston, MA: Birkhäuser, p. 97, 1994.Sloane, N. J. A. Sequences A001918/M0242, A010554, A033948, A046144, A046145, A046146, and A046147 in "The On-Line Encyclopedia of Integer Sequences."Western, A. E. and Miller, J. C. P. Tables of Indices and Primitive Roots. Cambridge, England: Cambridge University Press, pp. xxxvii-xlii, 1968.

Referenced on Wolfram|Alpha

Primitive Root

Cite this as:

Weisstein, Eric W. "Primitive Root." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/PrimitiveRoot.html

Subject classifications