Explore BrainMass

Explore BrainMass

    Linear Congruences : Chinese Remainder Theorem

    This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

    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 .

    © BrainMass Inc. brainmass.com October 9, 2019, 6:21 pm ad1c9bdddf


    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.