Primitive root

From Encyclopedia of Mathematics
Revision as of 17:26, 7 February 2011 by (talk) (Importing text file)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

A primitive root of unity of order in a field is an element of such that and for any positive integer . The element generates the cyclic group of roots of unity of order .

If in there exists a primitive root of unity of order , then is relatively prime to the characteristic of . An algebraically closed field contains a primitive root of any order that is relatively prime with its characteristic. If is a primitive root of order , then for any that is relatively prime to , the element is also a primitive root. The number of all primitive roots of order is equal to the value of the Euler function if .

In the field of complex numbers, the primitive roots of order take the form

where and is relatively prime to .

A primitive root modulo is an integer such that

for , where is the Euler function. For a primitive root , its powers are incongruent modulo and form a reduced residue system modulo (cf. Reduced system of residues). Therefore, for each number that is relatively prime to one can find an exponent for which .

Primitive roots do not exist for all moduli, but only for moduli of the form , where is a prime number. In these cases, the multiplicative groups (cf. Multiplicative group) of reduced residue classes modulo have the simplest possible structure: they are cyclic groups of order . The concept of a primitive root modulo is closely related to the concept of the index of a number modulo .

Primitive roots modulo a prime number were introduced by L. Euler, but the existence of primitive roots modulo an arbitrary prime number was demonstrated by C.F. Gauss (1801).


[1] S. Lang, "Algebra" , Addison-Wesley (1984)
[2] C.F. Gauss, "Disquisitiones Arithmeticae" , Yale Univ. Press (1966) (Translated from Latin)
[3] I.M. Vinogradov, "Elements of number theory" , Dover, reprint (1954) (Translated from Russian)



[a1] G.H. Hardy, E.M. Wright, "An introduction to the theory of numbers" , Oxford Univ. Press (1979)
How to Cite This Entry:
Primitive root. Encyclopedia of Mathematics. URL:
This article was adapted from an original article by L.V. Kuz'minS.A. Stepanov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article