1
$\begingroup$

I'm having trouble understanding this theorem:

If $g$ is a primitive root of $m$, then the remainders modulo $m$ of $g,g^2,...,g^{\varphi (m)}$ are the $\varphi (m)$ natural numbers that are relatively prime with $m$.

The proof goes like this:

$g$ is a primitive root, so $\gcd(g,m) = 1 \implies \gcd(g^k,m) = 1 \text{ for } \ k = 1,...,\varphi(m)$. We also know that $g^j \equiv g^k \text{ (mod } m)$ is equivalent to $j \equiv k \text{ (mod } \varphi(m))$, so those remainders are unique.

I think it says that we have $\varphi(m)$ numbers, being $g^1,...,g^{\varphi(m)}$, relatively prime with $m$ and dividing each of those with $m$ yields a different remainder. I don't see where it implies that those remainders are relatively prime to $m$. Perhaps I could understand it if there was a proof of the statement "the remainder of $a$ divided by $b$ with $a$ and $b$ relatively prime, is a prime number" but I don't even know if this is true. So can someone help me with this proof?

Thank you!

$\endgroup$
6
  • $\begingroup$ Start with the definition of primitive root. Then consider the implication of any two powers $g^i$ and $g^j$ for $1\le i \lt j \le \varphi(m)$ being equal. $\endgroup$
    – hardmath
    Nov 10, 2017 at 19:23
  • $\begingroup$ Re: "The remainder of a divided by b...." The remainder can be anything. The remainder of 9 divided by 5 is 4. $\endgroup$
    – DanielWainfleet
    Nov 10, 2017 at 21:06
  • 1
    $\begingroup$ If $p$ is prime and $j\in \Bbb N$ then $p|g^j$ iff $p|g.$ So if $\gcd(g,m)=1$ then $\gcd (g^j,m)=1$ for all $j\in \Bbb N.$ Because if $\gcd(g^j,m)>1$ then $g^j$ and $m $ are both divisible by some prime $p,$ but then $p|g$ and $p|m.$ $\endgroup$
    – DanielWainfleet
    Nov 10, 2017 at 21:13
  • $\begingroup$ @hardmath $g^i \equiv g^j$ (mod $m$) $\iff i \equiv j$ (mod $\varphi(m)$). So if $i \neq j$, $g^i$ gives a certain remainder mod $\varphi(m)$ and $g^j$ gives another remainder mod $\varphi(m)$. But, e.g. $\varphi(10) = 4$, and $9>4$ is also relatively prime to 10 but this can't be reached mod $m$. So that's what I still don't understand... $\endgroup$
    – user402016
    Nov 11, 2017 at 10:06
  • 1
    $\begingroup$ What you say is correct, but there are only $\varphi(m)$ elements to generate (the residues mod $m$ that are coprime to $m$). When we get to $g^{\varphi(m)}$ that equals $1 \bmod m$, and the powers of primitive root $g$ begin to repeat after that. $\endgroup$
    – hardmath
    Nov 11, 2017 at 13:28

1 Answer 1

Reset to default
1
$\begingroup$

We know that $\gcd(g,m)=1$ (and thus they have no common factors). This is enough to say that $\gcd(g^i,m)=1$ for all $i\in \Bbb N$. (And extending this into the modular world is simply taking one step in the Euclidean algorithm).

Also, in case this part is giving you trouble, we know that $k=\phi(m)$ is the smallest positive number for which a primitive root $g$ has $g^k\equiv 1 \bmod m$, from the definition of a primitive root.

So when $g^j\equiv g^\ell \bmod m$, with $j<\ell$, it's clear that $g^{\ell-j}\equiv 1$ and thus that $\phi(m) \mid \ell{-}j$, which can also be expressed as $\ell\equiv j \bmod \phi(n)$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .