Show Equivalence: $a^d \equiv 1 \pmod n$

[evinda]

Hello! (Wave)

Suppose that $p,q$ are two distinct primes , $n=pq$ and $d=gcd(p-1,q-1)$.
I want to show that if $a^{n-1} \equiv 1 \pmod{n}$ for some $a$ then $a^d \equiv 1 \pmod{n}$.

That's what I have tried:

$
a^{pq-1}\equiv 1 \pmod n \Rightarrow a^{pq-p+p-1}\equiv 1 \pmod n \Rightarrow a^{p(q-1)+(p-1)}\equiv 1 \pmod n \Rightarrow a^{Ad+Bd}\equiv 1 \pmod n$ for some $A,B \in \mathbb{Z}$.
Then we have $ a^{d(A+B)}\equiv 1 \pmod n \Rightarrow \left (a^{d}\right )^{A+B}\equiv 1 \pmod n$.

But from this, we cannot deduce that $a^d \equiv 1 \pmod{n}$, can we? (Thinking)

 

[I like Serena]

Hello! (Wave)

Suppose that $p,q$ are two distinct primes , $n=pq$ and $d=gcd(p-1,q-1)$.
I want to show that if $a^{n-1} \equiv 1 \pmod{n}$ for some $a$ then $a^d \equiv 1 \pmod{n}$.

That's what I have tried:

$
a^{pq-1}\equiv 1 \pmod n \Rightarrow a^{pq-p+p-1}\equiv 1 \pmod n \Rightarrow a^{p(q-1)+(p-1)}\equiv 1 \pmod n \Rightarrow a^{Ad+Bd}\equiv 1 \pmod n$ for some $A,B \in \mathbb{Z}$.
Then we have $ a^{d(A+B)}\equiv 1 \pmod n \Rightarrow \left (a^{d}\right )^{A+B}\equiv 1 \pmod n$.

But from this, we cannot deduce that $a^d \equiv 1 \pmod{n}$, can we? (Thinking)

Hey evinda! (Smile)

I haven't figured it out yet. :(

However, I can see a couple of approaches...
According to Euler we have:
$$a^{\phi(pq)} \equiv a^{(p-1)(q-1)} \equiv 1 \pmod{pq}$$
And according to the Chinese Remainder Theorem we have:
$$(a^{pq-1}, a^{pq-1}) \equiv (1 \bmod p,1 \bmod q)\quad\Rightarrow\quad a^{q-1}\equiv 1 \pmod p \quad\land\quad a^{p-1}\equiv 1 \pmod q$$
(Thinking)

 

[evinda]

We also have that $d=x(p-1)+y(q-1)$ for some $x,y \in \mathbb{Z}$ and from this and what you said above it follows that $a^d \equiv 1 \pmod{n}$. (Thinking)

 

[I like Serena]

We also have that $d=x(p-1)+y(q-1)$ for some $x,y \in \mathbb{Z}$ and from this and what you said above it follows that $a^d \equiv 1 \pmod{n}$. (Thinking)

Ah yes. Nice! (Smile)