2
$\begingroup$

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

  • 0
    Any $i$dea is welcome, it doesn't have to be based on group theory.2012-12-18

1 Answers 1

3

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

  • 0
    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.2012-12-18