Primitive root modulo n

In modular arithmetic, a number g is a primitive root modulo n if every number a coprime to n is congruent to a power of g modulo n. That is, g is a primitive root modulo n, if for every integer a coprime to n, there is some integer k for which g^k ≡ a (mod n). Such a value k is called the index or discrete logarithm of a to the base g modulo n. So g is a primitive root modulo n if and only if g is a generator of the multiplicative group of integers modulo n.

Gauss defined primitive roots in Article 57 of the Disquisitiones Arithmeticae (1801), where he credited Euler with coining the term. In Article 56 he stated that Lambert and Euler knew of them, but he was the first to rigorously demonstrate that primitive roots exist for a prime n. In fact, the Disquisitiones contains two proofs: The one in Article 54 is a nonconstructive existence proof, while the proof in Article 55 is constructive.

Elementary example[]

The number 3 is a primitive root modulo 7^[1] because

${\displaystyle {\begin{array}{rcrcrcrcrcr}3^{1}&=&3^{0}\times 3&\equiv &1\times 3&=&3&\equiv &3{\pmod {7}}\\3^{2}&=&3^{1}\times 3&\equiv &3\times 3&=&9&\equiv &2{\pmod {7}}\\3^{3}&=&3^{2}\times 3&\equiv &2\times 3&=&6&\equiv &6{\pmod {7}}\\3^{4}&=&3^{3}\times 3&\equiv &6\times 3&=&18&\equiv &4{\pmod {7}}\\3^{5}&=&3^{4}\times 3&\equiv &4\times 3&=&12&\equiv &5{\pmod {7}}\\3^{6}&=&3^{5}\times 3&\equiv &5\times 3&=&15&\equiv &1{\pmod {7}}\\3^{7}&=&3^{6}\times 3&\equiv &1\times 3&=&3&\equiv &3{\pmod {7}}\\\end{array}}}$

Here we see that the period of 3^k modulo 7 is 6. The remainders in the period, which are 3, 2, 6, 4, 5, 1, form a rearrangement of all nonzero remainders modulo 7, implying that 3 is indeed a primitive root modulo 7. This derives from the fact that a sequence (g^k modulo n) always repeats after some value of k, since modulo n produces a finite number of values. If g is a primitive root modulo n and n is prime, then the period of repetition is n − 1 . Curiously, permutations created in this way (and their circular shifts) have been shown to be Costas arrays.

Definition[]

If n is a positive integer, the integers between 0 and n − 1 that are coprime to n (or equivalently, the congruence classes coprime to n) form a group, with multiplication modulo n as the operation; it is denoted by ${\displaystyle \mathbb {Z} }$^×
_n, and is called the group of units modulo n, or the group of primitive classes modulo n. As explained in the article multiplicative group of integers modulo n, this multiplicative group (${\displaystyle \mathbb {Z} }$^×
_n) is cyclic if and only if n is equal to 2, 4, p^k, or 2p^k where p^k is a power of an odd prime number.^[2][3][4] When (and only when) this group ${\displaystyle \mathbb {Z} }$^×
_n is cyclic, a generator of this cyclic group is called a primitive root modulo n^[5] (or in fuller language primitive root of unity modulo n, emphasizing its role as a fundamental solution of the roots of unity polynomial equations X^m
− 1 in the ring ${\displaystyle \mathbb {Z} }$_n), or simply a primitive element of ${\displaystyle \mathbb {Z} }$^×
_n.

When ${\displaystyle \mathbb {Z} }$^×
_n is non-cyclic, such primitive elements mod n do not exist. Instead, each prime component of n has its own sub-primitive roots (see 15 in the examples below).

For any n (whether or not ${\displaystyle \mathbb {Z} }$^×
_n is cyclic), the order of ${\displaystyle \mathbb {Z} }$^×
_n is given by Euler's totient function φ(n) (sequence A000010 in the OEIS). And then, Euler's theorem says that a^φ(n) ≡ 1 (mod n) for every a coprime to n; the lowest power of a that is congruent to 1 modulo n is called the multiplicative order of a modulo n. In particular, for a to be a primitive root modulo n, φ(n) has to be the smallest power of a that is congruent to 1 modulo n.

Examples[]

For example, if n = 14 then the elements of ${\displaystyle \mathbb {Z} }$^×
_n are the congruence classes {1, 3, 5, 9, 11, 13}; there are φ(14) = 6 of them. Here is a table of their powers modulo 14:

 x     x, x2, x3, ... (mod 14)
 1 :   1
 3 :   3,  9, 13, 11,  5,  1 
 5 :   5, 11, 13,  9,  3,  1
 9 :   9, 11,  1
11 :  11,  9,  1
13 :  13,  1

The order of 1 is 1, the orders of 3 and 5 are 6, the orders of 9 and 11 are 3, and the order of 13 is 2. Thus, 3 and 5 are the primitive roots modulo 14.

For a second example let n = 15 . The elements of ${\displaystyle \mathbb {Z} }$^×
₁₅ are the congruence classes {1, 2, 4, 7, 8, 11, 13, 14}; there are φ(15) = 8 of them.

 x     x, x2, x3, ... (mod 15)
 1 :   1
 2 :   2,  4,  8, 1 
 4 :   4,  1
 7 :   7,  4, 13, 1
 8 :   8,  4,  2, 1
11 :  11,  1
13 :  13,  4,  7, 1
14 :  14,  1

Since there is no number whose order is 8, there are no primitive roots modulo 15. Indeed, λ(15) = 4, where λ is the Carmichael function. (sequence A002322 in the OEIS)

Table of primitive roots[]

Numbers ${\displaystyle n}$ that have a primitive root are of the shape

${\displaystyle n\in \{1,2,4,p^{k},2\cdot p^{k}\;\;|\;\;2<p{\text{ prime}};\;k\in \mathbb {N} \},}$

= {1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 17, 18, 19, ...} ^[6]

These are the numbers ${\displaystyle n}$ with ${\displaystyle \varphi (n)=\lambda (n),}$ kept also in the sequence A033948 in the OEIS.

The following table lists the primitive roots modulo n up to ${\displaystyle n=31}$:

${\displaystyle n}$	primitive roots modulo ${\displaystyle n}$	order ${\displaystyle \varphi (n),}$ (OEIS: A000010)	exponent ${\displaystyle \lambda (n),}$ (OEIS: A002322)
1	0	1	1
2	1	1	1
3	2	2	2
4	3	2	2
5	2, 3	4	4
6	5	2	2
7	3, 5	6	6
8		4	2
9	2, 5	6	6
10	3, 7	4	4
11	2, 6, 7, 8	10	10
12		4	2
13	2, 6, 7, 11	12	12
14	3, 5	6	6
15		8	4
16		8	4
17	3, 5, 6, 7, 10, 11, 12, 14	16	16
18	5, 11	6	6
19	2, 3, 10, 13, 14, 15	18	18
20		8	4
21		12	6
22	7, 13, 17, 19	10	10
23	5, 7, 10, 11, 14, 15, 17, 19, 20, 21	22	22
24		8	2
25	2, 3, 8, 12, 13, 17, 22, 23	20	20
26	7, 11, 15, 19	12	12
27	2, 5, 11, 14, 20, 23	18	18
28		12	6
29	2, 3, 8, 10, 11, 14, 15, 18, 19, 21, 26, 27	28	28
30		8	4
31	3, 11, 12, 13, 17, 21, 22, 24	30	30

Table of indices[]

This is Gauss's table of the primitive roots from the Disquisitiones. Unlike most modern authors he did not always choose the smallest primitive root. Instead, he chose 10 if it is a primitive root; if it isn't, he chose whichever root gives 10 the smallest index, and, if there is more than one, chose the smallest of them. This is not only to make hand calculation easier, but is used in § VI where the periodic decimal expansions of rational numbers are investigated.

The rows of the table are labelled with the prime powers n (excepting 2, 4, and 8) less than 100 (subset of sequence A185189 in the OEIS); the second column is a primitive root g (sequence A185268 in the OEIS) modulo that number. The columns further to the right are labelled with the primes p up to 100. The entry in row n and column p is the index i of p modulo n for the given primitive root g.

For example, in row n =11, g = 2 is given as the primitive root, and in column p = 5 the index is i = 4. This means that 2⁴ = 16 ≡ 5 (mod 11).

For the index of a composite number, add the indices of its prime factors p. For example, in row n =11, the index of p = 6 is the sum of the indices i = 1 and 8 for p = 2 and 3, and 2^{1 + 8} = 512 ≡ 6 (mod 11). The index of 25 is twice the index 5, and 2⁴⁺⁴ = 2⁸ = 256 ≡ 25 (mod 11). (Of course, since 25 ≡ 3 (mod 11), the index for 3 is 8).

The table is straightforward for the modules n which are odd prime powers. But the powers of 2 (n =16, 32, 64) do not have primitive roots; instead, the powers of 5 account for one-half of the odd numbers p modulo n, namely those which are p ≡ 5 or 1 (mod 8), and their negatives −p modulo n account for the other half. This is, because all powers of 5 are congruent to either 5 or 1 (modulo 8); the columns headed by numbers p ≡ 3 or 7 (mod 8) contain the index of its negative −p.

For example, modulo n =32 the index for 17 is 4, and 5⁴ = 625 ≡ 17 (mod 32); but the index for p =7 is given as 2, and 5² = 25 ≡ −7 ≡ −p (mod 32), since 7 ≢ 5 or 1 (mod 8).
Furthermore, the index of p =17×7 ≡ 23 (mod 32) (note that 23 ≡ 7 (mod 8)) would be 4+2=6, because 5⁶ = 15625 ≡ −23 ≡ −p (mod 32).
And the index of p = 7×7 ≡ 17 (mod 32) (note that 17 ≡ 1 (mod 8)) is 2+2=4, as already mentioned.
Moreover, the index of p =3×3×7 ≡ 31 (mod 32) (note that 31 ≡ 7 (mod 8)) would be 3+3+2= 8 ≡ 0 (mod 8), because 5⁸ = 390625 ≡ 1 ≡ 5⁰ ≡ −31 ≡ −p (mod 32).

(An entry − indicates that p is not coprime to n (it then cannot be power of some primitive root g).)

Primitive roots g and indices for a given module n
(the entries in the cells of the columns to the right of p = are the indices i with gⁱ ≡ p (mod n)

n ‖	g ‖	p =	2	3	5	7	11		13	17	19	23	29		31	37	41	43	47		53	59	61	67	71		73	79	83	89	97
3	2		1
5	2		1	3
7	3		2	1	5
9	2		1	−	5	4
11	2		1	8	4	7
13	6		5	8	9	7	11
16	5		−	3	1	2	1		3
17	10		10	11	7	9	13		12
19	10		17	5	2	12	6		13	8
23	10		8	20	15	21	3		12	17	5
25	2		1	7	−	5	16		19	13	18	11
27	2		1	−	5	16	13		8	15	12	11
29	10		11	27	18	20	23		2	7	15	24
31	17		12	13	20	4	29		23	1	22	21	27
32	5		−	3	1	2	5		7	4	7	6	3		0
37	5		11	34	1	28	6		13	5	25	21	15		27
41	6		26	15	22	39	3		31	33	9	36	7		28	32
43	28		39	17	5	7	6		40	16	29	20	25		32	35	18
47	10		30	18	17	38	27		3	42	29	39	43		5	24	25	37
49	10		2	13	41	−	16		9	31	35	32	24		7	38	27	36	23
53	26		25	9	31	38	46		28	42	41	39	6		45	22	33	30	8
59	10		25	32	34	44	45		28	14	22	27	4		7	41	2	13	53		28
61	10		47	42	14	23	45		20	49	22	39	25		13	33	18	41	40		51	17
64	5		−	3	1	10	5		15	12	7	14	11		8	9	14	13	12		5	1	3
67	12		29	9	39	7	61		23	8	26	20	22		43	44	19	63	64		3	54	5
71	62		58	18	14	33	43		27	7	38	5	4		13	30	55	44	17		59	29	37	11
73	5		8	6	1	33	55		59	21	62	46	35		11	64	4	51	31		53	5	58	50	44
79	29		50	71	34	19	70		74	9	10	52	1		76	23	21	47	55		7	17	75	54	33		4
81	11		25	−	35	22	1		38	15	12	5	7		14	24	29	10	13		45	53	4	20	33		48	52
83	50		3	52	81	24	72		67	4	59	16	36		32	60	38	49	69		13	20	34	53	17		43	47
89	30		72	87	18	7	4		65	82	53	31	29		57	77	67	59	34		10	45	19	32	26		68	46	27
97	10		86	2	11	53	82		83	19	27	79	47		26	41	71	44	60		14	65	32	51	25		20	42	91	18
‖ n	‖ g	p =	2	3	5	7	11		13	17	19	23	29		31	37	41	43	47		53	59	61	67	71		73	79	83	89	97

Properties[]

Gauss proved^[7] that for any prime number p (with the sole exception of p = 3), the product of its primitive roots is congruent to 1 modulo p.

He also proved^[8] that for any prime number p, the sum of its primitive roots is congruent to μ(p − 1) modulo p, where μ is the Möbius function.

For example,

p = 3,	μ(2) = −1.	The primitive root is 2.
p = 5,	μ(4) = 0.	The primitive roots are 2 and 3.
p = 7,	μ(6) = 1.	The primitive roots are 3 and 5.
p = 31,	μ(30) = −1.	The primitive roots are 3, 11, 12, 13, 17, 21, 22 and 24.

E.g., the product of the latter primitive roots is ${\displaystyle 2^{6}\cdot 3^{4}\cdot 7\cdot 11^{2}\cdot 13\cdot 17=970377408\equiv 1{\pmod {31}}}$, and their sum is ${\displaystyle 123\equiv -1\equiv \mu (31-1){\pmod {31}}}$.

If ${\displaystyle a}$ is a primitive root modulo the prime ${\displaystyle p}$, then ${\displaystyle a^{\frac {p-1}{2}}\equiv -1{\pmod {p}}}$.

Artin's conjecture on primitive roots states that a given integer a that is neither a perfect square nor −1 is a primitive root modulo infinitely many primes.

Finding primitive roots[]

No simple general formula to compute primitive roots modulo n is known.^[a][b] There are however methods to locate a primitive root that are faster than simply trying out all candidates. If the multiplicative order (its exponent) of a number m modulo n is equal to ${\displaystyle \varphi (n)}$ (the order of ${\displaystyle \mathbb {Z} }$^×
_n), then it is a primitive root. In fact the converse is true: If m is a primitive root modulo n, then the multiplicative order of m is ${\displaystyle \varphi (n)=\lambda (n)~.}$ We can use this to test a candidate m to see if it is primitive.

For ${\displaystyle n>1}$ first, compute ${\displaystyle \varphi (n)~.}$ Then determine the different prime factors of ${\displaystyle \varphi (n)}$, say p₁, ..., p_k. Finally, compute

${\displaystyle g^{\varphi (n)/p_{i}}{\bmod {n}}\qquad {\mbox{ for }}i=1,\ldots ,k}$

using a fast algorithm for modular exponentiation such as exponentiation by squaring. A number g for which these k results are all different from 1 is a primitive root.

The number of primitive roots modulo n, if there are any, is equal to^[9]

${\displaystyle \varphi \left(\varphi (n)\right)}$

since, in general, a cyclic group with r elements has ${\displaystyle \varphi (r)}$ generators, with r being the integers coprime to n, which generate n.

For prime n, this equals ${\displaystyle \varphi (n-1)}$, and since ${\displaystyle n/\varphi (n-1)\in O(\log \log n)}$ the generators are very common among {2, ..., n−1} and thus it is relatively easy to find one.^[10]

If g is a primitive root modulo p, then g is also a primitive root modulo all powers p^k unless g^p−1 ≡ 1 (mod p²); in that case, g + p is.^[11]

If g is a primitive root modulo p^k, then g is also a primitive root modulo all smaller powers of p.

If g is a primitive root modulo p^k, then either g or g + p^k (whichever one is odd) is a primitive root modulo 2p^k.^[11]

Finding primitive roots modulo p is also equivalent to finding the roots of the (p − 1)st cyclotomic polynomial modulo p.

Order of magnitude of primitive roots[]

The least primitive root g_p modulo p (in the range 1, 2, ..., p − 1 ) is generally small.

Upper bounds[]

Burgess (1962) proved^[12] that for every ε > 0 there is a C such that ${\displaystyle g_{p}\leq C\,p^{{\frac {1}{4}}+\varepsilon }~.}$

Grosswald (1981) proved^[12] that if ${\displaystyle p>e^{e^{24}}\approx 10^{11504079571}}$, then ${\displaystyle g_{p}<p^{0.499}~.}$

Shoup (1990, 1992) proved,^[13] assuming the generalized Riemann hypothesis, that g_p = O(log⁶ p).

Lower bounds[]

Fridlander (1949) and Salié (1950) proved^[12] that there is a positive constant C such that for infinitely many primes g_p > C log p .

It can be proved^[12] in an elementary manner that for any positive integer M there are infinitely many primes such that M < g_p < p − M .

Applications[]

A primitive root modulo n is often used in cryptography, including the Diffie–Hellman key exchange scheme. Sound diffusers have been based on number-theoretic concepts such as primitive roots and quadratic residues.^[14][15]

See also[]

Footnotes[]

References[]

Sources[]