let $q-1=d(p-1).$ since $\gcd(a,q)=1,$ we have $a^{q-1} \equiv 1 \mod q.$ also since $\gcd(a,p)=1,$ we have: $a^{p-1} \equiv 1 \mod p,$ which gives us: $a^{q-1}=(a^{p-1})^d \equiv 1 \mod p.$
so we showed that both $p$ and $q$ divide $a^{q-1}-1,$ and thus $pq$ must also divide $a^{q-1} - 1. \ \ \ \square$