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 \Rightarrow 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?