MATH135 Study Guide - Final Guide: Prime Number, Chinese Remainder Theorem, Mathematical Induction

• School: University of Waterloo
• Department: Mathematics
• Course: MATH135
• Professor: All

Document Summary

These are the warm-up exercises and recommended problems taken from all the extra practice sets presented in random order. We now inves- tigate what happens if the moduli are not coprime. (a) consider the following two systems of linear congruences: (cid:26) n 2 n 10. B : (mod 12) (mod 18) (cid:26) n 5 n 11. Determine which one has solutions and which one has no solutions. For the one with solutions, give the complete solutions to the system. For the one with no solutions, explain why no solutions exist. (b) let a1, a2 be integers, and let m1, m2 be positive integers. S : (cid:26) n a1 n a2 (mod m1) (mod m2) Using your observations in (a), complete the following two statements. The system s has a solution if and only if. 3: let a and b be integers. Use induction to prove the following statements. (a) for n 2, (b) let a =