Difference between revisions of "Primitive root"
(Importing text file) |
m (link) |
||
Line 13: | Line 13: | ||
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074630/p07463031.png" /></td> </tr></table> | <table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074630/p07463031.png" /></td> </tr></table> | ||
− | for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074630/p07463032.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074630/p07463033.png" /> is the Euler function. For a primitive root <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074630/p07463034.png" />, its powers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074630/p07463035.png" /> are incongruent modulo <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074630/p07463036.png" /> and form a reduced residue system modulo <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074630/p07463037.png" /> (cf. [[Reduced system of residues|Reduced system of residues]]). Therefore, for each number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074630/p07463038.png" /> that is relatively prime to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074630/p07463039.png" /> one can find an exponent <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074630/p07463040.png" /> <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074630/p07463041.png" /> for which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074630/p07463042.png" />. | + | for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074630/p07463032.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074630/p07463033.png" /> is the Euler function. For a primitive root <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074630/p07463034.png" />, its powers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074630/p07463035.png" /> are incongruent modulo <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074630/p07463036.png" /> and form a reduced residue system modulo <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074630/p07463037.png" /> (cf. [[Reduced system of residues|Reduced system of residues]]). Therefore, for each number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074630/p07463038.png" /> that is relatively prime to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074630/p07463039.png" /> one can find an exponent <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074630/p07463040.png" /> <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074630/p07463041.png" /> for which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074630/p07463042.png" />: the [[index]] of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074630/p07463038.png" /> with respect to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074630/p07463034.png" />. |
Primitive roots do not exist for all moduli, but only for moduli <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074630/p07463043.png" /> of the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074630/p07463044.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074630/p07463045.png" /> is a prime number. In these cases, the multiplicative groups (cf. [[Multiplicative group|Multiplicative group]]) of reduced residue classes modulo <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074630/p07463046.png" /> have the simplest possible structure: they are cyclic groups of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074630/p07463047.png" />. The concept of a primitive root modulo <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074630/p07463048.png" /> is closely related to the concept of the [[Index|index]] of a number modulo <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074630/p07463049.png" />. | Primitive roots do not exist for all moduli, but only for moduli <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074630/p07463043.png" /> of the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074630/p07463044.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074630/p07463045.png" /> is a prime number. In these cases, the multiplicative groups (cf. [[Multiplicative group|Multiplicative group]]) of reduced residue classes modulo <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074630/p07463046.png" /> have the simplest possible structure: they are cyclic groups of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074630/p07463047.png" />. The concept of a primitive root modulo <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074630/p07463048.png" /> is closely related to the concept of the [[Index|index]] of a number modulo <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074630/p07463049.png" />. |
Revision as of 22:04, 19 December 2014
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
: the index of
with respect to
.
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).
References
[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) |
Comments
References
[a1] | G.H. Hardy, E.M. Wright, "An introduction to the theory of numbers" , Oxford Univ. Press (1979) |
Primitive root. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Primitive_root&oldid=18612