# a question on congruences

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

-
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

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$.
Suppose that $n$ has a primitive root. It is not hard to show that in that case, $(2)$ implies $(1)$.