Namespaces
Variants
Actions

Difference between revisions of "Primitive root"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (link)
 
(2 intermediate revisions by the same user not shown)
Line 1: Line 1:
A primitive root of unity of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074630/p0746301.png" /> in a field <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074630/p0746302.png" /> is an element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074630/p0746303.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074630/p0746304.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074630/p0746305.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074630/p0746306.png" /> for any positive integer <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074630/p0746307.png" />. The element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074630/p0746308.png" /> generates the [[Cyclic group|cyclic group]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074630/p0746309.png" /> of roots of unity of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074630/p07463010.png" />.
+
{{TEX|done}}
  
If in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074630/p07463011.png" /> there exists a primitive root of unity of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074630/p07463012.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074630/p07463013.png" /> is relatively prime to the characteristic of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074630/p07463014.png" />. An [[Algebraically closed field|algebraically closed field]] contains a primitive root of any order that is relatively prime with its characteristic. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074630/p07463015.png" /> is a primitive root of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074630/p07463016.png" />, then for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074630/p07463017.png" /> that is relatively prime to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074630/p07463018.png" />, the element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074630/p07463019.png" /> is also a primitive root. The number of all primitive roots of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074630/p07463020.png" /> is equal to the value of the [[Euler function|Euler function]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074630/p07463021.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074630/p07463022.png" />.
+
==Primitive root of unity==
 +
A primitive root of unity of order $m$ in a field $K$ is an element $\zeta$ of $K$ such that $\zeta^m = 1$ and $\zeta^r \neq 1$ for any positive integer $r < m$. The element $\zeta$ generates the [[cyclic group]] $\mu_m$ of roots of unity of order $m$.
  
In the field of complex numbers, the primitive roots of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074630/p07463023.png" /> take the form
+
If in $K$ there exists a primitive root of unity of order $m$, then $m$ is relatively prime to the [[Characteristic of a field|characteristic]] of $K$. An [[algebraically closed field]] contains a primitive root of any order that is relatively prime with its characteristic. If $\zeta$ is a primitive root of order $m$, then for any $k$ that is relatively prime to $m$, the element $\zeta^k$ is also a primitive root. The number of all primitive roots of order $m$ is equal to the value of the [[Euler function]] $\phi(m)$ if $\mathrm{hcf}(m,\mathrm{char}(K)) = 1$.
  
<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/p07463024.png" /></td> </tr></table>
+
In the field of [[complex number]]s, there are primitive roots of unity of every order: those of order $m$ take the form
 +
$$
 +
\cos \frac{2\pi k}{m} + i \sin  \frac{2\pi k}{m}
 +
$$
 +
where $0 < k < m$ and $k$ is relatively prime to $m$.
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074630/p07463025.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074630/p07463026.png" /> is relatively prime to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074630/p07463027.png" />.
+
==Primitive root in modular arithmetic==
 +
A primitive root modulo $m$ is an integer $g$ such that
 +
$$
 +
g^{\phi(m)} \equiv 1 \pmod m\ \ \ \text{and}\ \ \ g^\gamma \not\equiv 1 \pmod m
 +
$$
 +
for $1 \le \gamma < \phi(m )$, where $\phi(m)$ is the Euler function. For a primitive root $g$, its powers $g^0=1,\ldots,g^{\phi(m)-1}$ are incongruent modulo $m$ and form a [[reduced system of residues]] modulo $m$. Therefore, for each number $a$ that is relatively prime to $m$ one can find an exponent $\gamma$, $0 \le \gamma < \phi(m)$ for which $g^\gamma \equiv a \pmod m$: the [[index]] of $a$ with respect to $g$.
  
A primitive root modulo <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074630/p07463029.png" /> is an integer <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074630/p07463030.png" /> such that
+
Primitive roots do not exist for all moduli, but only for moduli $m$ of the form $2,4, p^a, 2p^a$, where $p>2$ is a prime number. In these cases, the [[multiplicative group]]s of reduced residue classes modulo $m$ have the simplest possible structure: they are cyclic groups of order $\phi(m)$. The concept of a primitive root modulo $m$ is closely related to the concept of the [[index]] of a number modulo $m$.
 
 
<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" />: 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 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).
 
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====
 
====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  S. Lang,  "Algebra" , Addison-Wesley  (1984)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  C.F. Gauss,  "Disquisitiones Arithmeticae" , Yale Univ. Press  (1966)  (Translated from Latin)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  I.M. Vinogradov,  "Elements of number theory" , Dover, reprint  (1954)  (Translated from Russian)</TD></TR></table>
+
<table>
 +
<TR><TD valign="top">[1]</TD> <TD valign="top">  S. Lang,  "Algebra" , Addison-Wesley  (1984)</TD></TR>
 +
<TR><TD valign="top">[2]</TD> <TD valign="top">  C.F. Gauss,  "Disquisitiones Arithmeticae" , Yale Univ. Press  (1966)  (Translated from Latin)</TD></TR>
 +
<TR><TD valign="top">[3]</TD> <TD valign="top">  I.M. Vinogradov,  "Elements of number theory" , Dover, reprint  (1954)  (Translated from Russian)</TD></TR>
 +
</table>
  
  
Line 28: Line 36:
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  G.H. Hardy,  E.M. Wright,  "An introduction to the theory of numbers" , Oxford Univ. Press  (1979)</TD></TR></table>
+
<table>
 +
<TR><TD valign="top">[a1]</TD> <TD valign="top">  G.H. Hardy,  E.M. Wright,  "An introduction to the theory of numbers" , Oxford Univ. Press  (1979)</TD></TR>
 +
</table>

Latest revision as of 07:46, 20 December 2014


Primitive root of unity

A primitive root of unity of order $m$ in a field $K$ is an element $\zeta$ of $K$ such that $\zeta^m = 1$ and $\zeta^r \neq 1$ for any positive integer $r < m$. The element $\zeta$ generates the cyclic group $\mu_m$ of roots of unity of order $m$.

If in $K$ there exists a primitive root of unity of order $m$, then $m$ is relatively prime to the characteristic of $K$. An algebraically closed field contains a primitive root of any order that is relatively prime with its characteristic. If $\zeta$ is a primitive root of order $m$, then for any $k$ that is relatively prime to $m$, the element $\zeta^k$ is also a primitive root. The number of all primitive roots of order $m$ is equal to the value of the Euler function $\phi(m)$ if $\mathrm{hcf}(m,\mathrm{char}(K)) = 1$.

In the field of complex numbers, there are primitive roots of unity of every order: those of order $m$ take the form $$ \cos \frac{2\pi k}{m} + i \sin \frac{2\pi k}{m} $$ where $0 < k < m$ and $k$ is relatively prime to $m$.

Primitive root in modular arithmetic

A primitive root modulo $m$ is an integer $g$ such that $$ g^{\phi(m)} \equiv 1 \pmod m\ \ \ \text{and}\ \ \ g^\gamma \not\equiv 1 \pmod m $$ for $1 \le \gamma < \phi(m )$, where $\phi(m)$ is the Euler function. For a primitive root $g$, its powers $g^0=1,\ldots,g^{\phi(m)-1}$ are incongruent modulo $m$ and form a reduced system of residues modulo $m$. Therefore, for each number $a$ that is relatively prime to $m$ one can find an exponent $\gamma$, $0 \le \gamma < \phi(m)$ for which $g^\gamma \equiv a \pmod m$: the index of $a$ with respect to $g$.

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

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)
How to Cite This Entry:
Primitive root. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Primitive_root&oldid=35730
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