# Show that $a^{q-1} \equiv 1 \pmod{pq}$

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}$$

• Damn, I lost the type-off this time. But hint: Chinese Remainder Theorem. – anon Jun 9 '12 at 4:49

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}.$

Note that $p-1\mid q-1$ means that $q-1=k(p-1)$ for some $k$. Thus, $$a^{p-1}\equiv 1\bmod p$$ implies that $$a^{q-1} = a^{k(p-1)} = (a^{p-1})^k\equiv 1^k= 1\bmod p.$$ Now use the Chinese Remainder Theorem.

You know that:

$a^{p-1} \equiv 1$ mod $p$

but $(p-1)|(q-1)$ so this means that

$a^{q-1} \equiv 1$ mod $p$.

Now you may use the Chinese remainer theorem with your first congruence to tell you that

$a^{q-1} \equiv 1$ mod $pq$