proof of properties of primitive roots

The material in the main article is conveniently recast in terms of the groups ${(\mathbb{Z}/m\mathbb{Z})}^{\times }$, the multiplicative group of units in $\mathbb{Z}/m\mathbb{Z}$. Note that the order of this group is exactly $\varphi (m)$ where $\varphi$ is the Euler phi function. Then saying that an integer $g$ is a primitive root of $m$ is equivalent to saying that the residue class of $g(modm)$ generates ${(\mathbb{Z}/m\mathbb{Z})}^{\times }$.

Proof.

(of Theorem):
The proof of the theorem is an immediate consequence of the structure of ${(\mathbb{Z}/m\mathbb{Z})}^{\times }$ as an abelian group; ${(\mathbb{Z}/m\mathbb{Z})}^{\times }$ is cyclic precisely for $m=2,4,p^k$, or $2p^k$.∎

Proof.

(of Proposition):

1. Restated, this says that if the residue class of $g(modm)$ generates ${(\mathbb{Z}/m\mathbb{Z})}^{\times }$, 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 }$; this is obvious.

2. Restated, this says that $g(modm)$ generates ${(\mathbb{Z}/m\mathbb{Z})}^{\times }$ if and only if $g$ has exact order $m$, which is also obvious.

3. If $g(modm)$ generates ${(\mathbb{Z}/m\mathbb{Z})}^{\times }$, then $g$ has exact order $\varphi (m)$ and thus $g^s=g^t(modm)$ if and only if $g^{s-t}=1$ if and only if $\varphi (m)\mid s-t$.

4. Suppose $g$ generates ${(\mathbb{Z}/m\mathbb{Z})}^{\times }$. Then ${(g^k)}^r=1$ if and only if $g^{kr}=1$ if and only if $\varphi (m)\mid kr$. Clearly we can choose if and only if $\gcd (k,\varphi (m))>1$.

5. This follows immediately from (4).∎