Search Results for “primitive root modulo n”

Source: Primitive root modulo n

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.
This was first proved by Gauss.

Elementary example

primitive

Definition

Examples

Table of primitive roots

primitive

root

N} \},}

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

n

{\displaystyle n}

with

φ
(
n
)
=
λ
(
n
)
,

{\displaystyle \varphi (n)=\lambda (n),}

kept also in the sequence A033948 in the OEIS.
The following table lists the primitive roots modulo n up to

n
=
31

{\displaystyle n=31}

:

Properties

Gauss proved 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 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.
For example,

E.g., the product of the latter primitive roots is

2

6

⋅

3

4

⋅
7
⋅

11

2

⋅
13
⋅
17
=
970377408
≡
1

(
mod

31
)

{\displaystyle 2^{6}\cdot 3^{4}\cdot 7\cdot 11^{2}\cdot 13\cdot 17=970377408\equiv 1{\pmod {31}}}

, and their sum is

123
≡
−
1
≡
μ
(
31
−
1
)

(
mod

31
)

{\displaystyle 123\equiv -1\equiv \mu (31-1){\pmod {31}}}

.
If

a

{\displaystyle a}

is a primitive root modulo the prime

p

{\displaystyle p}

, then

a

p
−
1

2

≡
−
1

(
mod

p
)

{\displaystyle a^{\frac {p-1}{2}}\equiv -1{\pmod {p}}}

.
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.

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 (its exponent) of a number m modulo n is equal to

φ
(
n
)

{\displaystyle \varphi (n)}

(the order of

Z

{\displaystyle \mathbb {Z} }

×n), 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

φ
(
n
)
=
λ
(
n
)

.

{\displaystyle \varphi (n)=\lambda (n)~.}

We can use this to test a candidate m to see if it is primitive.
For

n
>
1

{\displaystyle n>1}

first, compute

φ
(
n
)

.

{\displaystyle \varphi (n)~.}

Then determine the different prime factors of

φ
(
n
)

{\displaystyle \varphi (n)}

, say p1, ..., pk. Finally, compute

g

φ
(
n
)

/

p

i

mod

n

for

i
=
1
,
…
,
k

{\displaystyle g^{\varphi (n)/p_{i}}{\bmod {n}}\qquad {\mbox{ for }}i=1,\ldots ,k}

using a fast algorithm for modular exponentiation such as exponentiation by squaring. A number g 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

φ

(

φ
(
n
)

)

{\displaystyle \varphi \left(\varphi (n)\right)}

since, in general, a cyclic group with r elements has

φ
(
r
)

{\displaystyle \varphi (r)}

generators.
For prime n, this equals

φ
(
n
−
1
)

{\displaystyle \varphi (n-1)}

, and since

n

/

φ
(
n
−
1
)
∈
O
(
log
⁡
log
⁡
n
)

{\displaystyle n/\varphi (n-1)\in O(\log \log n)}

the generators are very common among {2, ..., n−1} 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 (mod p2); in that case, g + p is.
If g is a primitive root modulo pk, then g is also a primitive root modulo all smaller powers of p.
If g is a primitive root modulo pk, then either g or g + pk (whichever one is odd) is a primitive root modulo 2pk.
Finding primitive roots modulo p is also equivalent to finding the roots of the (p − 1)st cyclotomic polynomial modulo p.

Order of magnitude of primitive roots

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

= Upper bounds

=
Burgess (1962) proved that for every ε > 0 there is a C such that

g

p

≤
C

p

1
4

+
ε

.

{\displaystyle g_{p}\leq C\,p^{{\frac {1}{4}}+\varepsilon }~.}

Grosswald (1981) proved that if

p
>

e

e

24

≈

10

11504079571

{\displaystyle p>e^{e^{24}}\approx 10^{11504079571}}

, then

g

p

<

p

0.499

.

{\displaystyle g_{p}

Shoup (1990, 1992) proved, assuming the generalized Riemann hypothesis, that gp = O(log6 p).

= Lower bounds

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

Footnotes

References

Sources

External links

Weisstein, Eric W. "Primitive Root". MathWorld.
Holt. "Quadratic residues and primitive roots". Mathematics. Michigan Tech.
"Primitive roots calculator". BlueTulip.