# Prove that if $g$ is a primitive root of $n$ and $g*b \equiv 1 \pmod n$, then $b$ is also a primitive root of $n$.

Some useful facts I am trying to use:

If the multiplicative group $U_n$ modulo $n$ is a cyclic group, a generator $g$ of $U_n$ is called a primitive root of $n$.

if $g$ in $U_n$ is a primitive root, then $|g|= \phi(n)$ where $\phi$ is the euler phi function.

An element $g$ in $U_n$ is a primitive root if and only if $g^{\phi(n)/p}$ not congruent to $1\pmod n$ for each prime dividing $\phi(n)$

-
But why is the title different from the content? – awllower Mar 24 '13 at 5:52
Typesetting tip: since you are going to need dollars anyway (the character) to get math symbols, subscripts, etc., put them around the entire math formulas, then the whole thing will look better. – Marc van Leeuwen Mar 24 '13 at 6:08
This question and the one here: math.stackexchange.com/questions/339317 are the same - Presumably, two people from the same class, given the timing. – Glen O Mar 24 '13 at 6:11
There is an inconsistency in the question in the title: $g$ and $b$ are elements in a cyclic group, yet their product figures in a congruence relation, as if they were numbers. It could be that you identify $U_n$ with the cyclic group $(\Bbb Z/n\Bbb Z,{+})$, but then you should use addition, not multiplication (and the congruence would not be explicitly needed). I think you are just saying $b$ is the inverse of $g$; then you should omit the $\pmod n$ part. – Marc van Leeuwen Mar 24 '13 at 6:14
@GlenO Not merely a duplicate, the silly $\pmod n$ is present in the other question as well! – Marc van Leeuwen Mar 24 '13 at 6:16

## 3 Answers

Suppose that $g$ is a primitive root $\pmod n, \ g\cdot b\equiv1\pmod n$ and $b$ is not a primitive root $\pmod n$.

Then, use that $$(x\cdot y)^k\equiv x^k\cdot y^k \pmod n$$ to derive a contradiction.

-

Hint: if $\,C=\langle\,x\,\rangle\,$ is a cyclic group, then also $\,C=\langle\,x^{-1}\,\rangle\,$

-

$$\text{ If }ord_ma=d, ord_m(a^k)=\frac{d}{(d,k)}$$ (Proof @Page#95)

Here $b\equiv g^{-1}\pmod n$

So, $k=-1\implies (ord_ng,-1)=1$

and as $g$ is a primitive root $\pmod n,ord_ng=\phi(n)$

$\implies ord_n(b)=ord_n(g^{-1})=\frac{ord_ng}1=ord_ng=\phi(n)$

-