Proving $x ≡ y \pmod n $ if $x^a ≡ y^a \pmod n$

Question

How to prove $x ≡ y \pmod n $ if $x^a ≡ y^a \pmod n?$ We assume $a$ and $φ(n)$ are relatively prime and $x$ and $y$ are coprime.

I have no idea how to approach this. Any ideas?

Answer 1

We begin with:

Special case: $\gcd(x,n)=1$. In that case, $x$ has an inverse $\pmod n$ and we deduce that $$\left( x^{-1}y\right)^a\equiv 1 \pmod n$$

But then we know that the order of $x^{-1}y$ is a common divisor of $a$ and $\varphi(n)$, hence the order is $1$, hence $x^{-1}y\equiv 1 \pmod n$ which implies $x\equiv y \pmod n$ which is what we were trying to prove.

To conclude, suppose that $\gcd(x,n)=d>1$. Then there is some prime $p$ which divides both $x$ and $n$. But in that case we must have $$p\,|\,x^a-y^a\implies p\,|\,y^a\implies p\,|\,y$$

Whence $p\,|\,\gcd(x,y)$ but that contradicts the assumption that $\gcd(x,y)=1$ and we are done.