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

I would like to prove that the following 2 are equivalent:

  1. $\gcd(a,n)=1$ and $\exists x: x^m\equiv a \pmod n$

  2. $a^{\frac{\phi(n)}{d}}\equiv 1 \pmod n$ where $d=\gcd(m,\phi(n))$

$\phi(n)$ is Euler 's function.

I've proved $1\rightarrow 2$.

Any ideas on $2\rightarrow 1$?

share|cite|improve this question
May I ask why did you use finite-groups tag here? Did you mean any certain approach or view?? Thanks. – Babak S. Dec 18 '12 at 14:22
Both elements $x,a$ belong to the finite order group of Units of $Z_n$ since they are invertible. That is $a,x\in \mathbb{Z^*}_n $ . I've tried to prove $2 \rightarrow 1$ using the fact that since $\mathbb{Z}_n^{*}$ is abelian of finite order it is isomorphic to the direct product of cyclic groups of finite order but had no luck. – epsilon Dec 18 '12 at 14:27
Any idea is welcome, it doesn't have to be based on group theory. – epsilon Dec 18 '12 at 14:29
up vote 3 down vote accepted

It is not true that $(2)$ implies $(1)$. For example, let $n=8$, $m=2$, and $a=5$.

Here $\gcd(m,\varphi(n))=\gcd(2,4)=2$ and $5^2\equiv 1\pmod{8}$.

But $5$ is not a square modulo $8$: any odd square is congruent to $1$ modulo $8$.

Remark: There are many other counterexamples.

Suppose that $n$ has a primitive root. It is not hard to show that in that case, $(2)$ implies $(1)$.

share|cite|improve this answer
I was straggling 2 days for a proof… you’re so right. Indeed it is easy to prove it when n has a primitive root. Thank you so much. – epsilon Dec 18 '12 at 22:35

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.