The idea of this problem is to investigate solutions to x2≡1(mod pq) where p and q are distinct odd primes.
(a) Show that if p is an odd prime, then there are exactly two solutions modulo p to x2≡1(mod p).
(b) Find all pairs (a,b) Є Zp x Zq such that a2≡1(mod p) and b2≡1(mod q).
(c) Let p=17 and q=23. For each pair (a,b) from part (b), compute an integer modulo such that and .
(d) Verify that each integer found in part (c) is a solution to .
Congruences and the Chinese Remainder Theorem are investigated. The solution is detailed and well presented. The response received a rating of "5/5" from the student who originally posted the question.