# Show that r is a primitive root?

Show that if $r$ is a primitive root modulo the positive integer $m$, then ${\overline r }$ is also a primitive root modulo m if ${\overline r }$ is an inverse of $r$ modulo $m$.

My TA did not go over any proofs in my self study class. We just learned the topic and did some examples. I was wondering what this proof might look like. It seems it might help because it looks similar to the problems with examples.

• What is the definition of "primitive root" that you're using? – vadim123 Apr 29 '13 at 17:04

A primitive root of $m$ is a number $g$ such that $g,g^2,g^3, \dots, g^{\varphi(m)}$ are all incongruent modulo $m$. So $g$ is a primitive root of $m$ precisely if $g$ has order $\varphi(m)$ modulo $m$.

So it is enough to show that for any $x$, if $xy\equiv 1\pmod{m}$, then $x^k\equiv 1\pmod m$ if and only if $y^k\equiv 1\pmod{m}$. This is immediate, since $(xy)^k=x^ky^k$.

Since $r$ is a primitive root modulo $m$, we know it's invertible, so $$r^n\equiv 1\text{ (mod }m\text{)}\Longleftrightarrow (r^{-1})^n\equiv 1\text{ (mod }m\text{)}$$

• Oh, I apparently can't read today. My apologies. – Potato Apr 29 '13 at 17:58
• @Potato Haha, no problem. :) – Warren Moore Apr 29 '13 at 17:58