# properties of primitive roots

###### Definition.

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

###### Theorem.

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

###### Proposition.

Let $m>1$ be an integer.

1. 1.

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

2. 2.

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

3. 3.

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

4. 4.

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

5. 5.

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

Title properties of primitive roots PropertiesOfPrimitiveRoots 2013-03-22 16:20:47 2013-03-22 16:20:47 alozano (2414) alozano (2414) 4 alozano (2414) Theorem msc 11-00