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\phantom{\rule{veryverythickmathspace}{0ex}}(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 $2{p}^{k}$.
∎
Proof.
(of Proposition^{}):

1.
Restated, this says that if the residue class of $g\phantom{\rule{veryverythickmathspace}{0ex}}(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\phantom{\rule{veryverythickmathspace}{0ex}}(modm)$ generates ${(\mathbb{Z}/m\mathbb{Z})}^{\times}$ if and only if $g$ has exact order $m$, which is also obvious.

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

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 $\mathrm{gcd}(k,\varphi (m))>1$.

5.
This follows immediately from (4).∎
Title  proof of properties of primitive roots 

Canonical name  ProofOfPropertiesOfPrimitiveRoots 
Date of creation  20130322 18:43:48 
Last modified on  20130322 18:43:48 
Owner  rm50 (10146) 
Last modified by  rm50 (10146) 
Numerical id  4 
Author  rm50 (10146) 
Entry type  Proof 
Classification  msc 1100 