Namespaces
Variants
Actions

Primitive root

From Encyclopedia of Mathematics
Jump to: navigation, search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.


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=35734
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