Primitive root modulo n
In modular arithmetic, a number Template:Mvar is a primitive root modulo Template:Mvar if every number Template:Mvar coprime to Template:Mvar is congruent to a power of Template:Mvar modulo Template:Mvar. That is, Template:Mvar is a primitive root modulo Template:Mvar if for every integer Template:Mvar coprime to Template:Mvar, there is some integer Template:Mvar for which Template:MvarTemplate:Mvar ≡ Template:Mvar (mod Template:Mvar). Such a value Template:Mvar is called the index or discrete logarithm of Template:Mvar to the base Template:Mvar modulo Template:Mvar. So Template:Mvar is a primitive root modulo Template:Mvar if and only if Template:Mvar is a generator of the [[multiplicative group of integers modulo n|multiplicative group of integers modulo Template:Mvar]].
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 Template:Mvar. 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 Template:Nowrap. For all other values of n the multiplicative group of integers modulo n is not cyclic.<ref>{{#invoke:Template wrapper|{{#if:|list|wrap}}|_template=cite web |_exclude=urlname, _debug, id |url = https://mathworld.wolfram.com/{{#if:ModuloMultiplicationGroup%7CModuloMultiplicationGroup.html}} |title = Modulo Multiplication Group |author = Weisstein, Eric W. |website = MathWorld |access-date = |ref = Template:SfnRef }} </ref><ref name=":0">{{#invoke:citation/CS1|citation |CitationClass=web }}</ref><ref name="Vinogradov2003.pp=105-121">Template:Harv</ref> This was first proved by Gauss.<ref>Template:Harv</ref>
Elementary exampleEdit
The number 3 is a primitive root modulo 7<ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref> because <math display="block"> \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 \end{array} </math>
Here we see that the period of 3Template:Mvar 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 (Template:MvarTemplate:Mvar modulo Template:Mvar) always repeats after some value of Template:Mvar, since modulo Template:Mvar produces a finite number of values. If Template:Mvar is a primitive root modulo Template:Mvar and Template:Mvar is prime, then the period of repetition is Template:Nowrap Permutations created in this way (and their circular shifts) have been shown to be Costas arrays.
DefinitionEdit
If Template:Mvar is a positive integer, the integers from 1 to Template:Nowrap that are coprime to Template:Mvar (or equivalently, the congruence classes coprime to Template:Mvar) form a group, with multiplication modulo Template:Mvar as the operation; it is denoted by [[multiplicative group of integers modulo n|<math>\mathbb{Z}</math>Template:Su]], and is called the group of units modulo Template:Mvar, or the group of primitive classes modulo Template:Mvar. As explained in the article [[multiplicative group of integers modulo n|multiplicative group of integers modulo Template:Mvar]], this multiplicative group (<math>\mathbb{Z}</math>Template:Su) is cyclic if and only if Template:Mvar is equal to 2, 4, Template:Mvar, or 2Template:Mvar where Template:Mvar is a power of an odd prime number.<ref>{{#invoke:Template wrapper|{{#if:|list|wrap}}|_template=cite web |_exclude=urlname, _debug, id |url = https://mathworld.wolfram.com/{{#if:ModuloMultiplicationGroup%7CModuloMultiplicationGroup.html}} |title = Modulo Multiplication Group |author = Weisstein, Eric W. |website = MathWorld |access-date = |ref = Template:SfnRef }} </ref><ref name=":0" /><ref name="Vinogradov2003.pp=105–121">Template:Harvnb.</ref> When (and only when) this group <math>\mathbb{Z}</math>Template:Su is cyclic, a generator of this cyclic group is called a primitive root modulo Template:Mvar<ref>Template:Harvnb.</ref> (or in fuller language primitive root of unity modulo Template:Mvar, emphasizing its role as a fundamental solution of the roots of unity polynomial equations XTemplate:Su − 1 in the ring <math>\mathbb{Z}</math>Template:Mvar), or simply a primitive element of <math>\mathbb{Z}</math>Template:Su.
When <math>\mathbb{Z}</math>Template:Su is non-cyclic, such primitive elements mod Template:Mvar do not exist. Instead, each prime component of Template:Mvar has its own sub-primitive roots (see Template:Math in the examples below).
For any Template:Mvar (whether or not <math>\mathbb{Z}</math>Template:Su is cyclic), the order of <math>\mathbb{Z}</math>Template:Su is given by Euler's totient function Template:Mvar(Template:Mvar) (sequence A000010 in the OEIS). And then, Euler's theorem says that Template:Nowrap for every Template:Mvar coprime to Template:Mvar; the lowest power of Template:Mvar that is congruent to 1 modulo Template:Mvar is called the multiplicative order of Template:Mvar modulo Template:Mvar. In particular, for Template:Mvar to be a primitive root modulo Template:Mvar, Template:Nowrap has to be the smallest power of Template:Mvar that is congruent to 1 modulo Template:Mvar.
ExamplesEdit
For example, if Template:Nowrap then the elements of <math>\mathbb{Z}</math>Template:Su are the congruence classes {1, 3, 5, 9, 11, 13}; there are Template:Nowrap 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 Template:Nowrap The elements of <math>\mathbb{Z}</math>Template:Su are the congruence classes {1, 2, 4, 7, 8, 11, 13, 14}; there are Template:Nowrap 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, Template:Nowrap, where Template:Mvar is the Carmichael function. (sequence A002322 in the OEIS)
Table of primitive rootsEdit
Numbers <math>n</math> that have a primitive root are of the shape
- <math>n \in \{1, 2, 4, p^k, 2 \cdot p^k \; \; | \; \; 2 < p \text{ prime}; \; k \in \mathbb{N}\} ,</math>
- = {1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 17, 18, 19, ...}.<ref>Template:Harvnb.</ref>
These are the numbers <math>n</math> with <math>\varphi(n) = \lambda(n),</math> kept also in the sequence A033948 in the OEIS.
The following table lists the primitive roots modulo Template:Mvar up to <math>n=31</math>:
| Template:Tmath | primitive roots modulo Template:Tmath | order <math>\varphi(n),</math> (Template:Oeis) |
exponent <math>\lambda(n),</math> (Template:Oeis) |
|---|---|---|---|
| 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 |
PropertiesEdit
Gauss proved<ref>Template:Harvnb.</ref> that for any prime number Template:Mvar (with the sole exception of Template:Nowrap the product of its primitive roots is congruent to 1 modulo Template:Mvar.
He also proved<ref>Template:Harvnb.</ref> that for any prime number Template:Mvar, the sum of its primitive roots is congruent to Template:Mvar(Template:Mvar − 1) modulo Template:Mvar, where Template:Mvar is the Möbius function.
For example,
Template:Mvar = 3, Template:Mvar(2) = −1. The primitive root is 2. Template:Mvar = 5, Template:Mvar(4) = 0. The primitive roots are 2 and 3. Template:Mvar = 7, Template:Mvar(6) = 1. The primitive roots are 3 and 5. Template:Mvar = 31, Template:Mvar(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 <math>2^6\cdot 3^4\cdot 7\cdot 11^2\cdot 13\cdot 17 = 970377408 \equiv 1 \pmod{31}</math>, and their sum is <math>123 \equiv -1 \equiv \mu(31-1) \pmod{31}</math>.
If <math>a</math> is a primitive root modulo the prime <math>p</math>, then <math>a^\frac{p-1}{2}\equiv -1 \pmod p</math>.
Artin's conjecture on primitive roots states that a given integer Template:Mvar that is neither a perfect square nor −1 is a primitive root modulo infinitely many primes.
Finding primitive rootsEdit
No simple general formula to compute primitive roots modulo Template:Mvar is known.Template:EfnTemplate:Efn 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 Template:Mvar modulo Template:Mvar is equal to <math>\varphi(n)</math> (the order of <math>\mathbb{Z}</math>Template:Su), then it is a primitive root. In fact the converse is true: If Template:Mvar is a primitive root modulo Template:Mvar, then the multiplicative order of Template:Mvar is <math>\varphi(n) = \lambda(n)~.</math> We can use this to test a candidate Template:Mvar to see if it is primitive.
For <math>n > 1</math> first, compute <math>\varphi(n)~.</math> Then determine the different prime factors of <math>\varphi(n)</math>, say Template:Mvar1, ..., Template:Mvar. Finally, compute
- <math>g^{\varphi(n)/p_i}\bmod n \qquad\mbox{ for } i=1,\ldots,k</math>
using a fast algorithm for modular exponentiation such as exponentiation by squaring. A number Template:Mvar for which these Template:Mvar results are all different from 1 is a primitive root.
The number of primitive roots modulo Template:Mvar, if there are any, is equal to<ref>(sequence A010554 in the OEIS)</ref>
- <math>\varphi\left(\varphi(n)\right)</math>
since, in general, a cyclic group with Template:Mvar elements has <math>\varphi(r)</math> generators.
For prime Template:Mvar, this equals <math>\varphi(n-1)</math>, and since <math>n / \varphi(n-1) \in O(\log\log n)</math> the generators are very common among {2, ..., Template:Mvar−1} and thus it is relatively easy to find one.<ref name=Knuth-1998/>
If Template:Mvar is a primitive root modulo Template:Mvar, then Template:Mvar is also a primitive root modulo all powers Template:Mvar unless Template:MvarTemplate:Mvar−1 ≡ 1 (mod Template:Mvar2); in that case, Template:Mvar + Template:Mvar is.<ref name="Cohen1993"/>
If Template:Mvar is a primitive root modulo Template:Mvar, then Template:Mvar is also a primitive root modulo all smaller powers of Template:Mvar.
If Template:Mvar is a primitive root modulo Template:Mvar, then either Template:Mvar or Template:Mvar + Template:Mvar (whichever one is odd) is a primitive root modulo 2Template:Mvar.<ref name="Cohen1993"/>
Finding primitive roots modulo Template:Mvar is also equivalent to finding the roots of the (Template:Mvar − 1)st cyclotomic polynomial modulo Template:Mvar.
Order of magnitude of primitive rootsEdit
The least primitive root Template:Mvar modulo Template:Mvar (in the range 1, 2, ..., Template:Nowrap is generally small.
Upper boundsEdit
Burgess (1962) proved<ref name="Ribenboim, p.24"/><ref>Template:Cite journal</ref> that for every ε > 0 there is a Template:Mvar such that <math>g_p \leq C\,p^{\frac{1}{4}+\varepsilon}.</math>
Grosswald (1981) proved<ref name="Ribenboim, p.24"/><ref>Template:Cite journal</ref> that if <math>p > e^{e^{24}} \approx 10^{11504079571}</math>, then <math>g_p < p^{0.499}.</math>
Shoup (1990, 1992) proved,<ref>Template:Harvnb.</ref> assuming the generalized Riemann hypothesis, that Template:Nowrap
Lower boundsEdit
Fridlander (1949) and Salié (1950) proved<ref name="Ribenboim, p.24"/> that there is a positive constant Template:Mvar such that for infinitely many primes Template:Nowrap
It can be proved<ref name="Ribenboim, p.24"/> in an elementary manner that for any positive integer Template:Mvar there are infinitely many primes such that Template:Mvar < Template:Mvar < Template:Nowrap
ApplicationsEdit
A primitive root modulo Template:Mvar is often used in pseudorandom number generators<ref>Template:Cite book</ref> 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.<ref name=Walker-1990/><ref name=Feldman/>
See alsoEdit
- Dirichlet character
- Full reptend prime
- Gauss's generalization of Wilson's theorem
- Multiplicative order
- Quadratic residue
- [[Root of unity modulo n|Root of unity modulo Template:Mvar]]
- Artin's conjecture on primitive roots
FootnotesEdit
ReferencesEdit
SourcesEdit
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.
Further readingEdit
External linksEdit
- {{#invoke:Template wrapper|{{#if:|list|wrap}}|_template=cite web
|_exclude=urlname, _debug, id |url = https://mathworld.wolfram.com/{{#if:PrimitiveRoot%7CPrimitiveRoot.html}} |title = Primitive Root |author = Weisstein, Eric W. |website = MathWorld |access-date = |ref = Template:SfnRef }}
- {{#invoke:citation/CS1|citation
|CitationClass=web }}
- {{#invoke:citation/CS1|citation
|CitationClass=web }}