Primitive root modulo n

In modular arithmetic, a number is a primitive root modulo if every number coprime to is congruent to a power of modulo. That is, is a primitive root modulo if for every integer coprime to, there is some integer for which ≡ . Such a value is called the index or discrete logarithm of to the base modulo. So is a primitive root modulo if and only if is a generator of the group of integers modulo n|multiplicative group of integers modulo ].
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. 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.
A primitive root exists if and only if n is 1, 2, 4, p^k or 2p^k, where p is an odd prime and. For all other values of n the multiplicative group of integers modulo n is not cyclic.
This was first proved by Gauss.

Elementary example

The number 3 is a primitive root modulo 7 because
Here we see that the period of 3 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, since modulo produces a finite number of values. If is a primitive root modulo and is prime, then the period of repetition is Permutations created in this way have been shown to be Costas arrays.

Definition

If is a positive integer, the integers from 1 to that are coprime to form a group, with multiplication modulo as the operation; it is denoted by [multiplicative group of integers modulo n|], and is called the group of units modulo, or the group of primitive classes modulo. As explained in the article multiplicative group of integers modulo , this multiplicative group is cyclic if and only if is equal to 2, 4,, or 2 where is a power of an odd prime number. When this group is cyclic, a generator of this cyclic group is called a primitive root modulo , or simply a primitive element of.
When is non-cyclic, such primitive elements mod do not exist. Instead, each prime component of has its own sub-primitive roots.
For any, the order of is given by Euler's totient function . And then, Euler's theorem says that for every coprime to ; the lowest power of that is congruent to 1 modulo is called the multiplicative order of modulo. In particular, for to be a primitive root modulo, has to be the smallest power of that is congruent to 1 modulo.

Examples

For example, if then the elements of are the congruence classes ; there are of them. Here is a table of their powers modulo 14:
x x, x², x³,...
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 are the congruence classes ; there are of them.
x x, x², x³,...
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 of the shape
These are the numbers with kept also in the sequence in the OEIS.
The following table lists the primitive roots modulo up to :

	primitive roots modulo	order	exponent
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

Properties

Gauss proved that for any prime number modulo, where is the Möbius function.
For example,
E.g., the product of the latter primitive roots is, and their sum is.
If is a primitive root modulo the prime, then.
Artin's conjecture on primitive roots states that a given integer 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 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 modulo is equal to [Euler's phi function|], then it is a primitive root. In fact the converse is true: If is a primitive root modulo, then the multiplicative order of is We can use this to test a candidate to see if it is primitive.
For first, compute Then determine the different prime factors of, say ₁,...,. Finally, compute
using a fast algorithm for modular exponentiation such as exponentiation by squaring. A number for which these results are all different from 1 is a primitive root.
The number of primitive roots modulo, if there are any, is equal to
since, in general, a cyclic group with elements has generators.
For prime, this equals, and since the generators are very common among and thus it is relatively easy to find one.
If is a primitive root modulo, then is also a primitive root modulo all powers unless ⁻¹ ≡ 1 ; in that case, + is.
If is a primitive root modulo, then is also a primitive root modulo all smaller powers of.
If is a primitive root modulo, then either or + is a primitive root modulo 2.
Finding primitive roots modulo is also equivalent to finding the roots of the st cyclotomic polynomial modulo.

Order of magnitude of primitive roots

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

Upper bounds

Burgess proved that for every ε > 0 there is a such that
Grosswald proved that if, then
Shoup proved, assuming the generalized Riemann hypothesis, that

Lower bounds

Fridlander and Salié proved that there is a positive constant such that for infinitely many primes
It can be proved in an elementary manner that for any positive integer there are infinitely many primes such that < <

Applications

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