In
modular arithmetic
In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his boo ...
, 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
≡ (mod ). Such a value is called the index or
discrete logarithm
In mathematics, for given real numbers ''a'' and ''b'', the logarithm log''b'' ''a'' is a number ''x'' such that . Analogously, in any group ''G'', powers ''b'k'' can be defined for all integers ''k'', and the discrete logarithm log''b ...
of to the base modulo . So is a ''primitive root modulo'' if and only if is a
generator of the
multiplicative group of integers modulo .
Gauss defined primitive roots in Article 57 of the ''
Disquisitiones Arithmeticae'' (1801), where he credited
Euler
Leonhard Euler ( , ; 15 April 170718 September 1783) was a Swiss mathematician, physicist, astronomer, geographer, logician and engineer who founded the studies of graph theory and topology and made pioneering and influential discoveries in ...
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
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
. 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
Although the general English usage of the adjective constructive is "helping to develop or improve something; helpful to someone, instead of upsetting and negative," as in the phrase "constructive criticism," in legal writing ''constructive'' has ...
.
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 (
modulo ) 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 (and their circular shifts) have been shown to be
Costas arrays.
Definition
If is a positive integer, the integers from 0 to that are
coprime to (or equivalently, the
congruence classes coprime to ) form a
group, with multiplication
modulo
In computing, the modulo operation returns the remainder or signed remainder of a division, after one number is divided by another (called the '' modulus'' of the operation).
Given two positive numbers and , modulo (often abbreviated as ) is ...
as the operation; it is denoted by
, 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
Cycle, cycles, or cyclic may refer to:
Anthropology and social sciences
* Cyclic history, a theory of history
* Cyclical theory, a theory of American political history associated with Arthur Schlesinger, Sr.
* Social cycle, various cycles in so ...
if and only if is equal to 2, 4, , or 2 where is a power of an odd
prime number
A prime number (or a prime) is a natural number greater than 1 that is not a Product (mathematics), product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime ...
.
[.] When (and only when) this group
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
), 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 (see in the examples below).
For any (whether or not
is cyclic), the order of
is given by
Euler's totient function
In number theory, Euler's totient function counts the positive integers up to a given integer that are relatively prime to . It is written using the Greek letter phi as \varphi(n) or \phi(n), and may also be called Euler's phi function. In ...
() . 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 In number theory, given a positive integer ''n'' and an integer ''a'' coprime to ''n'', the multiplicative order of ''a'' modulo ''n'' is the smallest positive integer ''k'' such that a^k\ \equiv\ 1 \pmod n.
In other words, the multiplicative ord ...
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
2, x
3, ... (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
are the congruence classes ; there are of them.
x x, x
2, x
3, ... (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
In number theory, a branch of mathematics, the Carmichael function of a positive integer is the smallest positive integer such that
:a^m \equiv 1 \pmod
holds for every integer coprime to . In algebraic terms, is the exponent of the multi ...
.
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
:
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,
:
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
In number theory, Artin's conjecture on primitive roots states that a given integer ''a'' that is neither a square number nor −1 is a primitive root modulo infinitely many primes ''p''. The conjecture also ascribes an asymptotic density to t ...
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 In number theory, given a positive integer ''n'' and an integer ''a'' coprime to ''n'', the multiplicative order of ''a'' modulo ''n'' is the smallest positive integer ''k'' such that a^k\ \equiv\ 1 \pmod n.
In other words, the multiplicative ord ...
(its
exponent) of a number modulo is equal to
(the order of
), 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 factor
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
s of
, say
1, ..., . 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, with being the integers coprime to , which generate .
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 ≡ 1 (mod 2); 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 + (whichever one is odd) is a primitive root modulo 2.
Finding primitive roots modulo is also equivalent to finding the roots of the ( − 1)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 (1962) proved that for every ''ε'' > 0 there is a such that
Grosswald (1981) proved that if , then
Shoup (1990, 1992) proved, assuming the generalized Riemann hypothesis, that
Lower bounds
Fridlander (1949) and Salié (1950) 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
A pseudorandom number generator (PRNG), also known as a deterministic random bit generator (DRBG), is an algorithm for generating a sequence of numbers whose properties approximate the properties of sequences of random numbers. The PRNG-generate ...
and cryptography
Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or '' -logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adv ...
, including the Diffie–Hellman key exchange scheme. Sound diffusers have been based on number-theoretic concepts such as primitive roots and quadratic residues.[
]
See also
* Dirichlet character
* Full reptend prime
In number theory, a full reptend prime, full repetend prime, proper primeDickson, Leonard E., 1952, ''History of the Theory of Numbers, Volume 1'', Chelsea Public. Co. or long prime in base ''b'' is an odd prime number ''p'' such that the Fermat ...
* Gauss's generalization of Wilson's theorem
* Multiplicative order In number theory, given a positive integer ''n'' and an integer ''a'' coprime to ''n'', the multiplicative order of ''a'' modulo ''n'' is the smallest positive integer ''k'' such that a^k\ \equiv\ 1 \pmod n.
In other words, the multiplicative ord ...
* Quadratic residue
In number theory, an integer ''q'' is called a quadratic residue modulo ''n'' if it is congruent to a perfect square modulo ''n''; i.e., if there exists an integer ''x'' such that:
:x^2\equiv q \pmod.
Otherwise, ''q'' is called a quadratic no ...
* Root of unity modulo
Footnotes
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.
*
*
*
*
*
Further reading
*.
External links
*
*
* {{cite web
, title = Primitive roots calculator
, website = BlueTulip
, url = http://www.bluetulip.org/programs/primitive.html
Modular arithmetic