How to Prove a Congruence in Modulo pq with Distinct Primes?

[mathmajor2013]

Question: Suppose p and q are distinct primes. Show that p^(q-1) + q^(p-1) is congruent to 1 modulo pq.

Answer: I know from Little Fermat Theorem that p^(q-1) is congruent to 1 modulo q and q^(p-1) is congruent to 1 modulo p, but I have no idea how to combine these two.

 

[CRGreathouse]

You know from the CRT that there is only one residue class mod pq that gives you A mod p and B mod q. So if 1 mod pq gives 1 mod p and 1 mod q, then you're done.