properties of primitive roots

Definition.

Let $m\mathrm{>}\mathrm{1}$ be an integer. An integer $g$ is said to be a primitive root of $m$ if $\gcd \mathit{}\mathrm{(}g\mathrm{,}m\mathrm{)}\mathrm{=}\mathrm{1}$ and the multiplicative order of $g$ is exactly $\varphi \mathit{}\mathrm{(}m\mathrm{)}$, where $\varphi$ is the Euler phi function. In other words, $g^{\varphi \mathit{}\mathrm{(}m\mathrm{)}}\mathrm{\equiv }\mathrm{1}\mathrm{mod}m$ and $g^n\mathrm{\ne }\mathrm{1}\mathrm{mod}m$ for any .

Theorem.

An integer $m\mathrm{>}\mathrm{1}$ has a primitive root if and only if $m$ is $\mathrm{2}\mathrm{,}\mathrm{4}\mathrm{,}{p}^k$ or $\mathrm{2}\mathit{}{p}^k$ for some $k\mathrm{\ge }\mathrm{1}$. In particular, every prime has a primitive root.

Proposition.

Let $m\mathrm{>}\mathrm{1}$ be an integer.

1. If $g$ is a primitive root of $m$ then the set $\{1,g,g^2,\mathrm{\dots },g^{\varphi (m)}\}$ is a complete set of representatives for ${(\mathbb{Z}/m\mathbb{Z})}^{\times }$.

2. If $\gcd (g,m)=1$ then $g$ is a primitive root of $m$ if and only if $g^{\varphi (m)/q}\ne 1modm$ for every prime divisor $q$ of $\varphi (m)$.

3. If $g$ is a primitive root of $m$, then $g^s\equiv g^{t}modm$ if and only if $s\equiv tmod\varphi (m)$. Thus $g^s\equiv 1modm$ if and only if $\varphi (m)$ divides $s$.

4. If $g$ is a primitive root of $m$, then $g^k$ is a primitive root of $m$ if and only if $\gcd (k,\varphi (m))=1$.

5. If $m$ has a primitive root then $m$ has exactly $\varphi (\varphi (m))$ incongruent primitive roots.