Assume that $p$ and $q$ are distinct add primes such that $p-1\mid q-1$. If $\gcd(a,pq)=1$ ,show that: $a^{q-1} \equiv 1 \pmod{pq}$
I have tried as follows: $a^{q-1} \equiv 1 \pmod{q} \quad \text{and} \quad a^{p-1} \equiv 1 \pmod{p}$ $\implies a^{(q-1)(p-1)} \equiv 1 \pmod{q} \quad \text{and} \quad a^{(q-1)(p-1)} \equiv 1 \pmod{p}$ $\implies a^{(q-1)(p-1)} \equiv 1 \pmod{pq}$
But then I am stuck - please help.