TOPICS
Search

Primitive Root


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

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

If n has a primitive root, then it has exactly phi(phi(n)) of them (Burton 1989, p. 188), which means that if p is a prime number, then there are exactly phi(p-1) incongruent primitive roots of p (Burton 1989). For n=1, 2, ..., the first few values of phi(phi(n)) are 1, 1, 1, 1, 2, 1, 2, 2, 2, 2, 4, 2, 4, 2, 4, 4, 8, ... (OEIS A010554). n has a primitive root if it is of the form 2, 4, p^a, or 2p^a, where p is an odd prime and a>=1 (Burton 1989, p. 204). The first few n for which primitive roots exist are 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 17, 18, 19, 22, ... (OEIS A033948), so the number of primitive root of order n for n=1, 2, ... are 0, 1, 1, 1, 2, 1, 2, 0, 2, 2, 4, 0, 4, ... (OEIS A046144).

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

ng(n)
21
32
43
52, 3
65
73, 5
92, 5
103, 7
112, 6, 7, 8
132, 6, 7, 11

The largest primitive roots for n=1, 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 n are given in the following table (OEIS A046145), which omits n when g(n) does not exist.

213839451583
324169751625
434339831632
5246510121665
6547510351675
7349310631692
9250310721732
10353210961783
11254511331792
132583118111812
143592121219119
17361212271935
18562312521945
19267212731972
22771713121993
23573513472023
25274513732065
26779313922112
27281214272145
292827146521811
31383214922233
34386315162263
37289315752272

Let p be any odd prime k>=1, and let

 s=sum_(j=1)^(p-1)j^k.
(1)

Then

 s={-1 (mod p)   for p-1|k; 0 (mod p)   for p-1k
(2)

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

 y=g^t (mod m),
(3)

where t=0, 1, ..., phi(m)-1, t is known as the index, and y is an integer. Kearnes (1984) showed that for any positive integer m, there exist infinitely many primes p such that

 m<g_p<p-m.
(4)

Call the least primitive root g_p. Burgess (1962) proved that

 g_p<=Cp^(1/4+epsilon)
(5)

for C and epsilon positive constants and p sufficiently large (Ribenboim 1996, p. 24).

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


See also

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

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 L-Series." Proc. London Math. Soc. 12, 193-206, 1962.Burton, D. M. "The Order of an Integer Modulo n," "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: 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.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, and A033948 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 Web Resource. https://mathworld.wolfram.com/PrimitiveRoot.html

Subject classifications