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 gk ≡ 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.
A primitive root exists if and only if n is 1, 2, 4, pk or 2pk, where p is an odd prime and k > 0.
For all other values of n the multiplicative group of integers modulo n is not cyclic.
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 (gk 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.
Permutations created in this way (and their circular shifts) have been shown to be Costas arrays.
If n is a positive integer, the integers from 1 to 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
×n is cyclic, a generator of this cyclic group is called a primitive root modulo n[8] (or in fuller language primitive root of unity modulo n, emphasizing its role as a fundamental solution of the roots of unity polynomial equations Xm − 1 in the ring
×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).
×n is given by Euler's totient function φ(n) (sequence A000010 in the OEIS).
Since there is no number whose order is 8, there are no primitive roots modulo 15.
The following table lists the primitive roots modulo n up to
: Gauss proved[10] 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[11] 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.
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.
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
In fact the converse is true: If m is a primitive root modulo n, then the multiplicative order of m is
The number of primitive roots modulo n, if there are any, is equal to[12] since, in general, a cyclic group with r elements has
[13] If g is a primitive root modulo p, then g is also a primitive root modulo all powers pk unless gp−1 ≡ 1 (mod p2); in that case, g + p is.
[14] Finding primitive roots modulo p is also equivalent to finding the roots of the (p − 1)st cyclotomic polynomial modulo p. The least primitive root gp modulo p (in the range 1, 2, ..., p − 1) is generally small.
Shoup (1990, 1992) proved,[18] assuming the generalized Riemann hypothesis, that gp = O(log6 p).
Fridlander (1949) and Salié (1950) proved[15] that there is a positive constant C such that for infinitely many primes gp > C log p. It can be proved[15] in an elementary manner that for any positive integer M there are infinitely many primes such that M < gp < p − M. A primitive root modulo n is often used in pseudorandom number generators[19] 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.
[20][21] The Disquisitiones Arithmeticae has been translated from Gauss's Ciceronian Latin into English and German.
The German edition includes all of his papers on number theory: all the proofs of quadratic reciprocity, the determination of the sign of the Gauss sum, the investigations into biquadratic reciprocity, and unpublished notes.