Solution: Since p 6= q are prime numbers, we have gcd(p, q) = 1. By Fermat’s
Little Theorem, p
q−1 ≡ 1 (mod q) . Clearly q
p−1 ≡ 0 (mod q) . Thus
p
q−1 + q
p−1 ≡ 1 (mod q) .
Exchanging the roles of p and q in the above argument, we prove that
p
q−1 + q
p−1 ≡ 1 (mod p)
