# [Math] CRT + Fermat’s Little Theorem

elementary-number-theory

I am seeking a proof for the following…

Suppose $p$ and $q$ are distinct primes. Show that $$p^{q-1} + q^{p-1} \equiv 1 \quad (\text{mod } pq)$$


I gather from Fermat's Little Theorem the following:
$$q^{p-1} \equiv 1 \quad (\text{mod } p)$$

and

$$p^{q-1} \equiv 1 \quad (\text{mod } q)$$

How can I use this knowledge to give a proof? I'm confident I can combine this with the Chinese Remainder Theorem, but I am stuck from here.

Write $a=p^{q-1}+q^{p-1}$. Immediately we have
$$\begin{cases} a\equiv 0^{\,q-1}+q^{p-1} \equiv 1 \mod p \\ a\equiv p^{q-1}+0^{\,p-1} \equiv 1 \mod q.\end{cases}$$
What does CRT tell us $a$ must be $\bmod pq$?