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?

Can anyone explain it please?


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 $.

  • $\begingroup$ 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? $\endgroup$ – ZFR Sep 30 '16 at 12:00
  • $\begingroup$ Superflous means unneccisery $\endgroup$ – Zelos Malum Sep 30 '16 at 12:01
  • $\begingroup$ So if $g$ and $m$ are not coprime than definition of primitive root becomes pointless. So $g$ and $m$ have to be coprime. Right? $\endgroup$ – ZFR Sep 30 '16 at 12:03
  • $\begingroup$ 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. $\endgroup$ – Starfall Sep 30 '16 at 12:04
  • $\begingroup$ 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? $\endgroup$ – ZFR Sep 30 '16 at 12:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.