Primitive root modulo n


Primitive root modulo n

In modular arithmetic, a branch of number theory, a primitive root modulo "n" is any number "g" with the property that any number coprime to "n" is congruent to a power of "g" (mod "n"). That is, if "g" is a primitive root (mod "n") and gcd("a", "n") = 1, then there is an integer "k" such that "g""k" ≡ "a" (mod "n"). "k" is called the index of "a".

Gauss defines primitive root in Article 57 of the Disquisitiones Arithmeticae (1801), where he credits Euler with coining the term. In Art. 56 he states that Lambert and Euler knew of them, but that his is the first rigorous demonstration that they exist. In fact, the "Disquisitiones" has two proofs: the one in Art. 54 is a nonconstructive existence proof, the one in Art. 55 is constructive.

Definition and examples

If "n" is a positive integer the congruence classes coprime to "n" form a group with multiplication modulo "n" as the operation; it is denoted by Z"n"× and is called the group of units (mod "n") or the group of primitive classes (mod "n"). As explained in the article multiplicative group of integers modulo n, this group is cyclic if and only if "n" is equal [Gauss, DA, arts 82-92] to 1, 2, 4, "p""k", or 2 "p""k" where "p""k" is a power of an odd prime number. A generator of this cyclic group is called a primitive root modulo "n", or a primitive element of Z"n"×.

The order of (i.e. the number of elements in) Z"n"× is given by Euler's totient function varphileft(n ight). Euler's theorem says that "a"φ("n") ≡ 1 (mod "n") for every "a" coprime to "n"; the lowest power of "a" which is ≡ 1 (mod "n") is called the multiplicative order of "a" (mod "n"). In other words, for "a" to be a primitive root modulo "n", φ("n") has to be the smallest power of "a" which is ≡ 1 (mod "n").

Take for example "n" = 14. The elements of Z14× are the congruence classes {1, 3, 5, 9, 11, 13}; there are φ(14) = 6 of them.

Here is a table of their powers (mod 14):

n n, n2, n3, ... (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 "n" = 15. The elements of Z15× are the congruence classes {1, 2, 4, 7, 8, 11, 13, 14}; there are φ(15) = 8 of them.

n n, n2, n3, ... (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 (mod 15).

Table of primitive roots

Given an appropropriate modulus "n", a primitive root "g" (mod "n") and a number "a" coprime to "n", the exponent to which "g" must be raised to be congruent to "a" (mod "n") is called the index of "a". It resembles a logarithm, in that multiplication becomes the addition of indices and exponentiation becomes multiplication of indices. It is usually denoted by ν("a"), i.e. "g"ν("a") ≡ "a" (mod "n").

This is Gauss's table of primitive roots from the "Disquisitiones". Unlike most modern authors he did not always choose the smallest primitive root. Instead, he chose 10 if it is a primitive root; if it isn't, he chose whichever root gives 10 the smallest index, and, if there is more than one, chose the smallest of them. This is not only to make hand calculation easier, but is used in § VI where the periodic decimal expansions of rational numbers are investigated.

The rows of the table are labeled with the prime powers (excepting 2, 4, and 8) less than 100; the second column is a primitive root modulo that number. The columns are labeled with the primes less than 97. The entry in row "p" column "q" is the index of "q" (mod "p") for the given root.

For example, in row 11, 2 is given as the primitive root, and in column 5 the entry is 4. This means that 24 = 16 ≡ 5 (mod 11).
For the index of a composite number, add the indices of its prime factors.
For example, in row 11, the index of 6 is the sum of the indices for 2 and 3: 21 + 8 = 512 ≡ 6 (mod 11). The index of 25 is twice the index 5: 28 = 256 ≡ 25 (mod 11). (Of course, since 25 ≡ 3 (mod 11), the entry for 3 is 8).

The table is straightforward for the odd prime powers. But the powers of 2, (16, 32, and 64) do not have primitive roots; instead, the powers of 5 account for one-half of the odd numbers less than the power of 2, and their negatives modulo the power of 2 account for the other half. All powers of 5 are ≡ 5 or 1 (mod 8); the columns headed by numbers ≡ 3 or 7 (mod 8) contain the index of its negative.

For example, (mod 32) the index for 7 is 2, and 52 = 25 ≡ –7 (mod 32), but the entry for 17 is 4, and 54 = 625 ≡ 17 (mod 32).

The sequence of smallest primitive roots may be found at OEIS|id=A046145.

Arithmetic facts

Gauss proved [Gauss, DA, art. 80] that for any prime number "p" (with the sole exception of 3) the product of its primitive roots is ≡ 1 (mod "p").

He also proved [Gauss, DA, art. 81] that for any prime number "p" the sum of its primitive roots is ≡ μ("p" – 1) (mod "p") where μ is the Möbius function.

For example

:"p" = 3, μ(2) = –1. The primitive root is 2.

:"p" = 5, μ(4) = 0. The primitive roots are 2 and 3.

:"p" = 7, μ(6) = 1. The primitive roots are 3 and 5.

:"p" = 31, μ(30) = –1. The primitive roots are 3, 11, 12, 13, 17 ≡ –14, 21 ≡ –10, 22 ≡ –9, and 24 ≡ –7.

Their product 970377408 ≡ 1 (mod 31) and their sum 123 ≡ –1 (mod 31).

::3×11 = 33 ≡ 2::12×13 = 156 ≡ 1::(–14)×(–10) = 140 ≡ 16::(–9)×(–7) = 63 ≡ 1, and 2×1×16×1 = 32 ≡ 1 (mod 31).

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 of a number "m" modulo "n" is equal to phileft(n ight) (the order of 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 phileft(n ight). We can use this to test for primitive roots.

First, compute phileft(n ight). Then determine the different prime factors of phileft(n ight), say "p"1,...,"p""k". Now, for every element "m" of Z"n"*, compute :m^{phi(n)/p_i}mod n qquadmbox{ for } i=1,ldots,kusing a fast algorithm for modular exponentiation such as exponentiation by squaring. A number "m" 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

:phileft(phileft(n ight) ight)

since, in general, a cyclic group with "r" elements has phileft(r ight) generators.

If "g" is a primitive root (mod "p") then "g" is a primitive root modulo all powers "p""k" unless "g" "p" – 1 ≡ 1 (mod "p"2); in that case, "g" + "p" is. [This and the next assertion are in Cohen, p.26]

If "g" is a primitive root (mod "p""k"), then "g" or "g" + "p""k" (whichever one is odd) is a primitive root (mod 2"p""k").

Order of magnitude of primitive roots

The least primitive root (mod "p") is generally small.

Let "g""p" be the smallest primitive root (mod "p") in the range 1, 2, ... "p"–1.

Fridlander (1949) and Salié (1950) proved [Ribenboim, p.24] that that there is a constant "C" such that for infinitely many primes "g""p" > "C" log "p".

It can be proved [Ribenboim, p.24] in an elementary manner that for any positive integer "M" there are infinitely many primes such that "M" < "g""p" < "p" &ndash; "M".

Burgess (1962) proved [Ribenboim, p.24] that for every &epsilon; > 0 there is a "C" such that g_p < Cp^{frac{1}{4}+epsilon}.

Grosswald (1981) proved [Ribenboim, p.24] that mbox{ if } p > e^{e^{24 mbox{ then }g_p < p^{0.499}

Shoup (1990, 1992) proved, [Bach & Shallit, p.254] assuming the generalized Riemann hypothesis, that "g""p" =O(log6 "p").

Uses

Primitive root modulo n is often used in cryptography, including the Diffie-Hellman Key Exchange Scheme.

ee also

* Artin's conjecture on primitive roots
* Dirichlet character
* Gauss' generalization of Wilson's theorem
* Order modulo n

Notes

References

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.

*citation
last1 = Gauss | first1 = Carl Friedrich
last2 = Clarke | first2 = Arthur A. (translator into English)
title = Disquisitiones Arithemeticae (Second, corrected edition)
publisher = Springer
location = New York
date = 1986
isbn = 0387962549

*citation
last1 = Gauss | first1 = Carl Friedrich
last2 = Maser | first2 = H. (translator into German)
title = Untersuchungen uber hohere Arithmetik (Disquisitiones Arithemeticae & other papers on number theory) (Second edition)
publisher = Chelsea
location = New York
date = 1965
isbn = 0-8284-0191-8

*citation
last1 = Bach | first1 = Eric
last2 = Shallit | first2 = Jeffrey
title = Algorithmic Number Theory (Vol I: Efficient Algorithms)
publisher = The MIT Press
location = Cambridge
date = 1966
isbn = 0-262-02045-5

*citation
last1 = Cohen | first1 = Henri
title = A Course in Computational Algebraic Number Theory
publisher = Springer
location = Berlin
date = 1993
isbn = 3-540-55640-0

*cite book
authorlink=Øystein Ore
last = Ore
first = Oystein
title = Number Theory and Its History
publisher = Dover
date = 1988
pages = 284-302
isbn = 0-486-65620-9

*citation
last1 = Ribenboim | first1 = Paulo
title = The New Book of Prime Number Records
publisher = Springer
location = New York
date = 1996
isbn = 0-387-94457-5

External links

This site has a [http://www.math.mtu.edu/mathlab/COURSES/holt/dnt/quadratic4.html primitive root calculator] applet.


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Primitive root — In mathematics, a primitive root may mean either* a primitive root modulo n in modular arithmetic, or * a primitive n th root of unity amongst the solutions of xn = 1 in a field.See also: primitive element …   Wikipedia

  • Root of unity — The 5th roots of unity in the complex plane In mathematics, a root of unity, or de Moivre number, is any complex number that equals 1 when raised to some integer power n. Roots of unity are used in many branches of mathematics, and are especially …   Wikipedia

  • Primitive element — In mathematics, the term primitive element can mean: * Primitive root modulo n , in number theory * Primitive element (field theory), an element that generates a given field extension * Primitive element (finite field), an element that generates… …   Wikipedia

  • Primitive polynomial — In field theory, a branch of mathematics, a primitive polynomial is the minimal polynomial of a primitive element of the finite extension field GF( p m ). In other words, a polynomial F(X) with coefficients in GF( p ) = Z/ p Z is a primitive… …   Wikipedia

  • Multiplicative group of integers modulo n — In modular arithmetic the set of congruence classes relatively prime to the modulus n form a group under multiplication called the multiplicative group of integers modulo n. It is also called the group of primitive residue classes modulo n. In… …   Wikipedia

  • Artin's conjecture on primitive roots — In mathematics, the Artin conjecture is a conjecture on the set of primes p modulo which a given integer a > 1 is a primitive root. The conjecture was made by Emil Artin to Helmut Hasse on September 27, 1927, according to the latter s diary.The… …   Wikipedia

  • Park–Miller random number generator — The Park–Miller random number generator (or the Lehmer random number generator) is a variant of linear congruential generator that operates in multiplicative group of integers modulo n. A general formula of a random generator (RNG) of this type… …   Wikipedia

  • Dirichlet character — In number theory, Dirichlet characters are certain arithmetic functions which arise from completely multiplicative characters on the units of . Dirichlet characters are used to define Dirichlet L functions, which are meromorphic functions with a… …   Wikipedia

  • Fermat number — In mathematics, a Fermat number, named after Pierre de Fermat who first studied them, is a positive integer of the form:F {n} = 2^{2^{ overset{n} {} + 1where n is a nonnegative integer. The first nine Fermat numbers are OEIS|id=A000215:As of|2008 …   Wikipedia

  • Primality test — A primality test is an algorithm for determining whether an input number is prime. Amongst other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating… …   Wikipedia