Primitive Root

A primitive root of a Prime $p$ is an Integer $g$ satisfying $1\leq g\leq p-1$ such that the residue classes of $g$, $g^2$, $g^3$, ..., $g^{p-1}=1$ are all distinct, i.e., $g$ (mod $p$) has Order $p-1$ (Ribenboim 1996, p. 22). If $p$ is a Prime Number, then there are exactly $\phi(p-1)$ incongruent primitive roots of $p$ (Burton 1989, p. 194).

More generally, if $(g,n)=1$ ($g$ and $n$ are Relatively Prime) and $g$ is of Order $\phi(n)$ modulo $n$, where $\phi(n)$ is the Totient Function, then $g$ is a primitive root of $n$ (Burton 1989, p. 187). In other words, $n$ has $g$ as a primitive root if $g^{\phi(n)}\equiv 1\ \left({{\rm mod\ } {n}}\right)$, but $g^k\not\equiv 1$ (mod $n$) for all positive integers $k<\phi(n)$. A primitive root of a number $n$ (but not necessarily the smallest primitive root for composite $n$) can be computed using the Mathematica ${}^{\scriptstyle\circledRsymbol}$ routine NumberTheory`NumberTheoryFunctions`PrimitiveRoot[n].

If $n$ has a primitive root, then it has exactly $\phi(\phi(n))$ of them (Burton 1989, p. 188). 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, ... (Sloane's A010554). $n$ has a primitive root if it is of the form 2, 4, a power $p^a$, or twice a power $2p^a$, where $p$ is an Odd Prime and $a\geq 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, ... (Sloane's 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, (Sloane's A046144).

The smallest primitive roots for the first few Integers $n$ are given in the following table (Sloane's A046145), which omits $n$ when $g(n)$ does not exist.

2	1	38	3	94	5	158	3
3	2	41	6	97	5	162	5
4	3	43	3	98	3	163	2
5	2	46	5	101	2	166	5
6	5	47	5	103	5	167	5
7	3	49	3	106	3	169	2
9	2	50	3	107	2	173	2
10	3	53	2	109	6	178	3
11	2	54	5	113	3	179	2
13	2	58	3	118	11	181	2
14	3	59	2	121	2	191	19
17	3	61	2	122	7	193	5
18	5	62	3	125	2	194	5
19	2	67	2	127	3	197	2
22	7	71	7	131	2	199	3
23	5	73	5	134	7	202	3
25	2	74	5	137	3	206	5
26	7	79	3	139	2	211	2
27	2	81	2	142	7	214	5
29	2	82	7	146	5	218	11
31	3	83	2	149	2	223	3
34	3	86	3	151	6	226	3
37	2	89	3	157	5	227	2

Let $p$ be any Odd Prime $k\geq 1$, and let

$$s\equiv \sum_{j=1}^{p-1} j^k.$$ (1)

Then

$$s=\cases{ -1 {\rm\ (mod\ } p) & for $p-1 \vert k$\cr 0 {\rm\ (mod\ } p) & for $p-1\notdiv k$.\cr}$$ (2)

For numbers $m$ with primitive roots, all $y$ satisfying $(p, y)=1$ are representable as

$$y\equiv g^t\ \left({{\rm mod\ } {m}}\right),$$ (3)

where $t=0$, 1, ..., $\phi(m)-1$, $t$ is known as the index, and $y$ is an Integer. Kearnes 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\leq C p^{1/4+\epsilon}$$ (5)

for $C$ and $\epsilon$ Positive constants and $p$ sufficiently large.

References

Abramowitz, M. and Stegun, C. 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.Guy, R. K. ``Primitive Roots.'' §F9 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 248-249, 1994.

Sloane, N. J. A. Sequences A046145 and A001918/M0242 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html and Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.