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.
Best Answer
Remember that you are told that $p-1$ divides $q-1$. Note that you have not yet used this hypothesis. That suggests that you should really try to use it somehow.
Since $p-1$ divides $q-1$, then there exists $k$ such that $q-1 = k(p-1)$. That means that, since $a^{p-1}\equiv 1\pmod{p}$, then $$1 \equiv 1^k \equiv (a^{p-1})^k \equiv a^{(p-1)k} = a^{q-1}\pmod{p}.$$
So now you have $a^{q-1}\equiv 1\pmod{q}$ and $a^{q-1}\equiv 1\pmod{p}.$