Primitive root modulo n


In modular arithmetic, a branch of number theory, 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 an integer k such that gk ≡ a. Such a value k is called the index or discrete logarithm of a to the base g modulo n. Note that 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, 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 other in Article 55 is constructive.

Elementary example

The number 3 is a primitive root modulo 7 because
Here we see that the period of 3k 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 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 have been shown to be Costas arrays.

Definition

If n is a positive integer, the integers between 0 and that are coprime to n form a group, with multiplication modulo n as the operation; it is denoted by Z, 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 is cyclic if and only if n is equal to 2, 4, pk, or 2pk where pk is a power of an odd prime number. When this group Z is cyclic, a generator of this cyclic group is called a primitive root modulo n, or simply a primitive element of Z. When Z is non-cyclic, such primitive elements mod n do not exist.
For any n, the order of Z is given by Euler's totient function φ. And then, Euler's theorem says that 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, φ has to be the smallest power of a that is congruent to 1 modulo n.

Examples

For example, if then the elements of Z are the congruence classes ; there are of them. Here is a table of their powers modulo 14:
x x, x2, x3,...
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. The elements of Z are the congruence classes ; there are of them.
x x, x2, x3,...
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,, where λ is the Carmichael function.

Table of primitive roots

Numbers that have a primitive root are
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 less than 100; the second column is a primitive root modulo that number. The columns are labelled with the primes less than 100. The entry in row p, column q is the index of q modulo p for the given root.
For example, in row 11, 2 is given as the primitive root, and in column 5 the entry is 4. This means that 24 = 16 ≡ 5.

For the index of a composite number, add the indices of its prime factors.
For example, in row 11, the index of 6 is the sum of the indices for 2 and 3:. The index of 25 is twice the index 5:..

The table is straightforward for the odd prime powers. But the powers of 2 do not have primitive roots; instead, the powers of 5 account for one-half of the odd numbers less than the power of 2, and their negatives modulo the power of 2 account for the other half. All powers of 5 are ≡ 5 or 1 ; the columns headed by numbers ≡ 3 or 7 contain the index of its negative.
For example, modulo 32 the index for 7 is 2, and 52 = 25 ≡ −7, but the entry for 17 is 4, and.

nroot235711 1317192329 3137414347 5359616771 7379838997
321
5213
73215
921*54
1121847
136589711
165*3121 3
171010117913 12
19101752126 138
231082015213 12175
25217*516 19131811
2721*51613 8151211
29101127182023 271524
3117121320429 231222127
325*3125 74763 0
37511341286 135252115 27
416261522393 31339367 2832
43283917576 4016292025 323518
47103018173827 342293943 5242537
491021341*16 931353224 738273623
5326259313846 284241396 452233308
59102532344445 281422274 74121353 28
61104742142345 2049223925 1333184140 5117
645*31105 151271411 89141312 513
671229939761 238262022 4344196364 3545
71625818143343 2773854 1330554417 59293711
7358613355 5921624635 116445131 535585044
79295071341970 74910521 7623214755 717755433 4
811125*35221 38151257 1424291013 455342033 4852
8350352812472 674591636 3260384969 1320345317 4347
893072871874 6582533129 5777675934 1045193226 684627
9710862115382 8319277947 2641714460 1465325125 20429118
nroot235711 1317192329 3137414347 5359616771 7379838997

The following table lists the primitive roots modulo n for n ≤ 72:
primitive roots modulo order primitive roots modulo order
101372, 5, 13, 15, 17, 18, 19, 20, 22, 24, 32, 3536
211383, 13, 15, 21, 29, 3318
3223924
4324016
52, 34416, 7, 11, 12, 13, 15, 17, 19, 22, 24, 26, 28, 29, 30, 34, 3540
6524212
73, 56433, 5, 12, 18, 19, 20, 26, 28, 29, 30, 33, 3442
844420
92, 564524
103, 74465, 7, 11, 15, 17, 19, 21, 33, 37, 4322
112, 6, 7, 810475, 10, 11, 13, 15, 19, 20, 22, 23, 26, 29, 30, 31, 33, 35, 38, 39, 40, 41, 43, 44, 4546
1244816
132, 6, 7, 1112493, 5, 10, 12, 17, 24, 26, 33, 38, 40, 45, 4742
143, 56503, 13, 17, 23, 27, 33, 37, 4720
1585132
1685224
173, 5, 6, 7, 10, 11, 12, 1416532, 3, 5, 8, 12, 14, 18, 19, 20, 21, 22, 26, 27, 31, 32, 33, 34, 35, 39, 41, 45, 48, 50, 5152
185, 116545, 11, 23, 29, 41, 4718
192, 3, 10, 13, 14, 15185540
2085624
21125736
227, 13, 17, 1910583, 11, 15, 19, 21, 27, 31, 37, 39, 43, 47, 5528
235, 7, 10, 11, 14, 15, 17, 19, 20, 2122592, 6, 8, 10, 11, 13, 14, 18, 23, 24, 30, 31, 32, 33, 34, 37, 38, 39, 40, 42, 43, 44, 47, 50, 52, 54, 55, 5658
2486016
252, 3, 8, 12, 13, 17, 22, 2320612, 6, 7, 10, 17, 18, 26, 30, 31, 35, 43, 44, 51, 54, 55, 5960
267, 11, 15, 1912623, 11, 13, 17, 21, 43, 53, 5530
272, 5, 11, 14, 20, 23186336
28126432
292, 3, 8, 10, 11, 14, 15, 18, 19, 21, 26, 27286548
3086620
313, 11, 12, 13, 17, 21, 22, 2430672, 7, 11, 12, 13, 18, 20, 28, 31, 32, 34, 41, 44, 46, 48, 50, 51, 57, 61, 6366
32166832
33206944
343, 5, 7, 11, 23, 27, 29, 31167024
3524717, 11, 13, 21, 22, 28, 31, 33, 35, 42, 44, 47, 52, 53, 55, 56, 59, 61, 62, 63, 65, 67, 68, 6970
36127224

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.
The sequence of smallest primitive roots modulo n are
For prime n, they are
The largest primitive roots modulo n are
For prime n, they are
Number of primitive roots modulo n are
For prime n, they are
Smallest prime > n with primitive root n are
Smallest prime with primitive root n are

Arithmetic facts

Gauss proved that for any prime number p, the product of its primitive roots is congruent to 1 modulo p.
He also proved that for any prime number p, the sum of its primitive roots is congruent to modulo p, where μ is the Möbius function.
For example,

What about adding up elements of this multiplicative group? As it happens, sums of two primitive roots add up to all elements of the index 2 subgroup of Z/n Z for even n, and to the whole group Z/n Z when n is odd:
Z/n Z× + Z/n Z× = Z/n Z or 2Z/n Z.

Finding primitive roots

No simple general formula to compute primitive roots modulo n is known. There are however methods to locate a primitive root that are faster than simply trying out all candidates. If the multiplicative order of a number m modulo n is equal to Euler's phi function|, 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 Euler's phi function|. We can use this to test a candidate m to see if it is primitive.
First, compute. Then determine the different prime factors of, say p1,..., pk. Finally, compute
using a fast algorithm for modular exponentiation such as exponentiation by squaring. A number m 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
since, in general, a cyclic group with r elements has generators. For prime n, this equals, and since the generators are very common among and thus it is relatively easy to find one.
If g is a primitive root modulo p, then g is also a primitive root modulo all powers pk unless gp−1 ≡ 1 ; in that case, g + p is.
If g is a primitive root modulo pk, then either g or g + pk is a primitive root modulo 2pk.
Finding primitive roots modulo p is also equivalent to finding the roots of the th cyclotomic polynomial modulo p.

Order of magnitude of primitive roots

The least primitive root gp modulo p is generally small.

Upper bounds

Burgess proved that for every ε > 0 there is a C such that
Grosswald proved that if, then.
Carella proved that there is a such that for all sufficiently large primes.
Shoup proved, assuming the generalized Riemann hypothesis, that gp = O.

Lower bounds

Fridlander and Salié 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.

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.