# 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 $\phi(m)$ where $\phi$ 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\pmod{m}$ 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. 1.

Restated, this says that if the residue class of $g\pmod{m}$ generates $(\mathbb{Z}/{m}\mathbb{Z})^{\times}$, then the set $\{1,g,g^{2},\ldots,g^{\phi(m)}\}$ is a complete set of representatives for $(\mathbb{Z}/{m}\mathbb{Z})^{\times}$; this is obvious.

2. 2.

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

3. 3.

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

4. 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 $\phi(m)\mid kr$. Clearly we can choose $r<\phi(m)$ if and only if $\gcd(k,\phi(m))>1$.

5. 5.

This follows immediately from (4).∎

Title proof of properties of primitive roots ProofOfPropertiesOfPrimitiveRoots 2013-03-22 18:43:48 2013-03-22 18:43:48 rm50 (10146) rm50 (10146) 4 rm50 (10146) Proof msc 11-00