Had the following problem on an exam, and couldn't crack it:

Show that if p and q are primes, then p^(q-1) + q^(p-1) == 1 (mod pq)

We know through Fermat each p^(q-1) == 1 (mod q) and q^(p-1) == 1(mod p). However I'm not sure how to combine the two.

I thought the CRT might help if we changed the system to p^(q) == p(mod q) and q^(p) == q (mod p).

If you think the problem easy, feel free to leave a hint rather than a solution so I have to work a bit -- I'd appreciate either