21127 Study Guide - Quiz Guide: Chinese Remainder Theorem, Natural Number, Burh
16 Dec 2015
School
Department
Course
Professor
Document Summary
Modular arithmetic lemma: let n n be given and xed. Let a, b z be arbitrary and xed. Suppose that a r mod n and b s mod n. then a + b r + s mod n a b r s mod n. Notice that this lemma tells us we can just work with the equivalence classes, mod n. whatever a, b we are given, we can just reduce them to their remainders, r and s, and work with those instead. The idea is that 0 r, s n 1, so they are guaranteed to be small, compared to a and b. Suppose a r mod n and b s mod n. this means k, (cid:96) z such that a = kn + r. Adding these equations yields a + b = (kn + r) + ((cid:96)n + s) = (k + (cid:96))n + (r + s)
