# Linear Congruences : Chinese Remainder Theorem

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 .

https://brainmass.com/math/linear-algebra/linear-congruences-chinese-remainder-theorem-85864

#### Solution Summary

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.

$2.19