# Primitive root modulo $n$

Definition 1: Let $m>1$ and $(a,m)=1$. We call that $\delta$ is the order of $a$ if $\delta$ - minimal natural number such that $a^{\delta}\equiv 1 \pmod m$.

Definition 2: Number $g$ is called primitive root modulo $m$ if its order is $\varphi(m)$, where $\varphi$ - Euler function.

These definition are from Vinogradov's book (russian edition). But in some references I noticed that one requires that $g$ have to me coprime with $m$. Is it necessary or not?

If $g$ is not coprime with $m$, then no power of $g$ can be $1$ modulo $m$, so the condition is superfluous. Indeed, this is a consequence of the fact that a power of $g$ is coprime with $m$ if and only if $g$ is coprime with $m$, which follows from unique factorization in $\mathbf Z$.
• So if $(g,m)=d>1$ then for any $k$ we have that $g^k\not\equiv 1 \pmod m$. What means "superfluous" in this context? – ZFR Sep 30 '16 at 12:00
• So if $g$ and $m$ are not coprime than definition of primitive root becomes pointless. So $g$ and $m$ have to be coprime. Right? – ZFR Sep 30 '16 at 12:03
• The definition of "primitive root", in itself, requires $g$ and $m$ to be coprime, in that it can never be satisfied otherwise. Asserting that they also have to be coprime is unnecessary for this reason. – Starfall Sep 30 '16 at 12:04
• Sorry for my English. $g$ and $m$ have to be coprime otherwise any degree of $g$ is NOT $\equiv 1 \pmod m$. Am I right? – ZFR Sep 30 '16 at 12:08