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