$x^a\equiv 1\pmod{p} \Rightarrow x \equiv 1\pmod{p}$

We know: $$\gcd(a,\phi(n))=1$$ and $$a,n,x>0$$.

Show that $$\gcd(x,n)=1$$ and $$x^a\equiv 1\pmod{p} \implies x \equiv 1\pmod{p}$$

My Attempt: Using Euler's Theorem I know that:

$$x^{\phi(n)}\equiv 1\pmod{p}$$ where $$\gcd(x,n)=1$$, is this enough to prove that $$\gcd(x,n)=1$$?

Deducing

Since $$x^a\equiv 1\pmod{p}$$ and $$x^{\phi(n)}\equiv 1\pmod{p}$$ and $$\gcd(a,\phi(n)=1$$ I can see why $$x\equiv 1\pmod{p}$$ would hold.

• Who is $p$ ? I ask this because you stated Euler's Theorem wrong , with $p$ in the place of $n$ .
– user252450
Dec 16 '15 at 15:37

From Bézout's theorem we can find two numbers $z$ and $y$ such that :

$$za+y \phi(n)=1$$

Using this it's straightforward to finish :

$$x \equiv x^{za+y \phi(n)} \equiv \left (x^a \right)^z \left(x^{\phi(n)} \right )^y \equiv 1^z \cdot 1^y \equiv 1 \pmod{n}$$ as wanted.

• Very nice, thank you! Can I conclude $\gcd(x,n)=1$ using Euler's?
– GRS
Dec 16 '15 at 15:36
• Can you please clarify the problem . Euler's theorem states that $x^{\phi(n)} \equiv 1\pmod{n}$ with the condition that $(x,n)=1$ . Can you please clarify who is $p$ ?
– user252450
Dec 16 '15 at 15:39
• So I can't use Euler's directly? I first need to show that $\gcd(x,n)=1$?
– GRS
Dec 16 '15 at 16:04

I'm assuming you want to prove that if $a,n,x>0$ and $x^a\equiv 1\pmod{n}$ and $\gcd(a,\phi(n))=1$, then $x\equiv 1\pmod{n}$.

Proof: $x^a\equiv 1\pmod{n}\implies \gcd(x,n)=1$.

$x^a\equiv 1\pmod{n}\iff \text{ord}_{n}(x)\mid a$.

By Euler's theorem $\text{ord}_n(x)\mid \phi(n)$.

Therefore $\text{ord}_n(x)\mid \gcd(a,\phi(n))=1$, so $\text{ord}_n(x)=1$, so $x\equiv 1\pmod n$.