Primitive root modulo n

In number theory, a number is a primitive root modulo  if every number coprime to is congruent to a power of modulo . In symbols, is a primitive root modulo  if for every integer coprime to , there is some integer for which .

Primitive roots only exist for some integers . Specifically, a primitive root exists modulo if and only if is 4, or for some odd prime number and some . This was first proved by Carl Friedrich Gauss. Gauss defined primitive roots in Article 57 of his Disquisitiones Arithmeticae (1801), where he credited Leonhard Euler with coining the term. In Article 56 he stated that Johann Heinrich Lambert and Euler knew of them, but he was the first to rigorously demonstrate that primitive roots exist for a prime number . 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.

An equivalent characterization is that is a primitive root modulo  if and only if is a generator of the multiplicative group of integers modulo . Thus, primitive roots exist if and only if this group is a cyclic group.

If is a primitive root modulo and , then the value is called the index or discrete logarithm of to the base modulo .

Elementary example

The number 3 is a primitive root modulo 7 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>

The remainders 3, 2, 6, 4, 5, 1 include each congruence class relatively prime to 7. Higher powers repeat the same pattern periodically.

The number of congruence classes relatively prime to the modulus is given by Euler's totient function applied to . In this case, that is . For a prime modulus , this period is always equal to , but this is not true for composite .

Definition

If is a positive integer, the integers from 1 to that are coprime to (or equivalently, the congruence classes coprime to ) form a group, with multiplication modulo as the operation; it is denoted by <math>\mathbb{Z}_n^\times</math>, 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 <math>\mathbb{Z}_n^\times</math> is cyclic if and only if is equal to 2, 4, , or where is a power of an odd prime number. When (and only when) this group <math>\mathbb{Z}_n^\times</math> is cyclic, a generator of this cyclic group is called a primitive root modulo (or in fuller language primitive root of unity modulo , emphasizing its role as a fundamental solution of the roots of unity polynomial equations X − 1 in the ring <math>\mathbb{Z}_n</math>), or simply a primitive element of <math>\mathbb{Z}_n^\times</math>.

When <math>\mathbb{Z}_n^\times</math> is non-cyclic, such primitive elements mod do not exist. Instead, each prime component of has its own sub-primitive roots (see in the examples below).

For any (whether or not <math>\mathbb{Z}_n^\times</math> is cyclic), the order of <math>\mathbb{Z}_n^\times</math> 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 satisfying .

Examples

For example, if then the elements of <math>\mathbb{Z}</math> are the congruence classes {1, 3, 5, 9, 11, 13}; there are 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 The elements of <math>\mathbb{Z}</math> are the congruence classes {1, 2, 4, 7, 8, 11, 13, 14}; there are 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, , where is the Carmichael function.

Table of primitive roots

Numbers <math>n</math> that have a primitive root are of the form

:<math>n \in \{1, 2, 4, p^k, 2 \cdot p^k \; \; | \; \; 2

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

These are the numbers <math>n</math> with <math>\varphi(n) = \lambda(n),</math> kept also in the sequence in the OEIS.

The following table lists the primitive roots modulo up to <math>n=31</math>:

{|class="wikitable"

!primitive roots modulo

!order <math>\varphi(n),</math> ()

!exponent <math>\lambda(n),</math> ()

|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 (with the sole exception of the product of its primitive roots is congruent to 1 modulo .

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

For example,

:{|

| = 3, || (2) = −1. || The primitive root is 2.

| = 5, || (4) = 0. || The primitive roots are 2 and 3.

| = 7, || (6) = 1. || The primitive roots are 3 and 5.

| = 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 <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 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 (its exponent) of a number modulo is equal to <math>\varphi(n)</math> (the order of <math>\mathbb{Z}</math>), then it is a primitive root. In fact the converse is true: If is a primitive root modulo , then the multiplicative order of is <math>\varphi(n) = \lambda(n)~.</math> We can use this to test a candidate 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 1, ..., . 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 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

:<math>\varphi\left(\varphi(n)\right)</math>

since, in general, a cyclic group with elements has <math>\varphi(r)</math> generators.

For prime , 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, ..., −1} and thus it is relatively easy to find one. that for every ε > 0 there is a such that <math>g_p \leq C\,p^{\frac{1}{4}+\varepsilon}.</math>

Grosswald (1981) proved that if <math>p > e^{e^{24 \approx 10^{11504079571}</math>, then <math>g_p < p^{0.499}.</math>

Shoup (1990, 1992) proved, assuming the generalized Riemann hypothesis, that

Lower bounds

Fridlander (1949) and Salié (1950) proved 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.-->

</references>

Sources

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.