Use the chinese remainder theorem to solve the systems of congruences: a. find x mod 77 if x ≡ 2 (mod 7) and x ≡ 4 (mod 11). b. x ≡ 2 (mod 3), x ≡ 3 (mod 4), x ≡ 1 (mod 5).

(a) Suppose we let



Modulo 7, we're left with , but we want a remainder of 2, so multiply 4 by 7 to assure that that remainder vanishes. So now



and , but modulo 11, we have . But we want the remainder to be 4, so multiply the first term by 11 to guarantee this. So we write



but now, we get a remainder of 1 modulo 7 and 6 modulo 11. To fix the first case, multiply the first term by 2. For the second case, first find the inverse of 6 modulo 11. We have , and , so the inverse is 2. Multiply the second term by 2, so that the second term's remainder modulo 11 becomes 1. Then multiply by 4, so that now



We have



(b) This is done similarly. Modulo 3, we want a remainder of 2, so we can start with



Then taken modulo 4, we need to multiply the first term by 2 and the third term by 4 to ensure the remainder becomes 3. The second term can be left alone.



Now taken modulo 5, we can multiply the first two terms by 5 and the third term by the inverse of . We have , so we multiply by 3.



Now



which means the smallest positive solution for the system would be .