0
$\begingroup$

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.

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

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.

$\endgroup$
3
  • $\begingroup$ Very nice, thank you! Can I conclude $\gcd(x,n)=1$ using Euler's? $\endgroup$
    – GRS
    Dec 16 '15 at 15:36
  • $\begingroup$ 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$ ? $\endgroup$
    – user252450
    Dec 16 '15 at 15:39
  • $\begingroup$ So I can't use Euler's directly? I first need to show that $\gcd(x,n)=1$? $\endgroup$
    – GRS
    Dec 16 '15 at 16:04
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.