 Solution

ID: past-exam-of-the-options-i-course-of-the-university-of-oxford/2009/c/c1/iv/solution

Because the primes are distinct, Fermat's little theorem gives

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

and

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

. The other term in each modulus vanishes. Therefore

p^{q - 1} + q^{p - 1} - 1 \equiv 0 (mod p), p^{q - 1} + q^{p - 1} - 1 \equiv 0 (mod q) .

The distinct primes are coprime, so their product divides this integer. Hence

p^{q - 1} + q^{p - 1} \equiv 1 (mod pq) .

 New to topics? Read the docs here!