Given a primitive root $r$ mod $p$, why is all $r^m, m\in GCD(\phi(p),m)=1$ incongruent primitive root to r?
So I don't really understand how incongruent primitive roots are found using this strategy is Elementary Number Theory and It's Applications.
The example I'll use is find incongruent primitive roots of 13.
So they do $\phi(\phi(13))=4$, so that means 4 incongruent primitive roots, which makes sense, then they show 2 is a primitive root, which makes sense because a primitive root can be found if $ord_{13}2=\phi(13)=12$, which it is in this case $2^{12}\equiv1(mod13)$, but then the answer skips ahead and says any $2^u$ where u is relatively prime to $\phi(13)=12$ is incongruent primitive root to 2. Why is this? Does this hold in general for all primitive roots?
Best Answer
If a primitive root exists, then this strategy will work.
The relatively prime condition ensures you have a primitive root, since $\mid g^m\mid=\mid g\mid/\operatorname {gcd}(m,\mid g\mid)$. This is a basic fact from the theory of cyclic groups.
Secondly, any two powers of a generator less than the order of the group are not congruent, quite trivially. That is, if $m,n\lt\mid G\mid$, we have $g^m\ne g^n$. For, if $g^m=g^n$, then $g^{m-n}=e$, contradicting that $g$ is primitive.