I am confused about primitive roots. My text defines primitive roots as the solutions for $a$ of the equation $\operatorname{ord}_m a = \phi(m)$ where $\operatorname{ord}_m a$ is defined as the minimal solution $t$ of the congruence $a^t\equiv 1\pmod{m}$. It is not clear to me if $a$ is always coprime to the modulus.
I understand there is a different definition of primitive root in Wikipedia
In my text, there is a proof that if $r$ is a primitive root, then for any integers $i$ and $j$, $r^i\equiv r^j \pmod{m}$ if and only if $i\equiv j \pmod{\phi}$. The proof goes from the proposition
$r^i\equiv r^j \pmod{m}$ to the proposition
$r^{i-j} \equiv 1 \pmod{m}$
This seems to require that $\gcd(r^j,m) = 1$? If so, how do we know this is true?
Some aspects of the discussion seem to assume that all primitive roots mod m are in the set
$\{a\mid\gcd(a,m)=1 \land 1\le a \lt m\}$ but others seems to allow primitive roots to be greater than the modulus and not require them to be coprime to the modulus. I am confused as to what is the range of primitive roots for a modulus.
Best Answer
If $\gcd(r^j,m)>1$ then there exists a prime $p$ that divides both $r^j$ and $m.$ By Euclid's lemma, $p$ divides $r.$ Then $\gcd(r,m)\ge p>1,$ which contradicts the fact that a power of $r$ is $1$ modulo $m.$ This is because the Bezout equation $$r\cdot r^{\varphi(m)-1}-mq=1$$ must be satisfied for some integer $q.$
By the way, you should make clear what the modulus is in your statements. For example, when you went from $r^i\equiv r^j$ to $i\equiv j,$ the moduli are different in the two congruences. The modulus is $m$ in the first one and $\varphi(m)$ in the second one.