Primitive root

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)

References

[a1]	G.H. Hardy, E.M. Wright, "An introduction to the theory of numbers" , Oxford Univ. Press (1979)