Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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: 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
up vote 3 down vote accepted

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.

share|cite|improve this answer

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

share|cite|improve this answer

$$\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)$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.