MACM 101 Lecture 28: Lecture 28 Part 1_ Chinese Remainder Theorem

• School: Simon Fraser University
• Department: Math & Comp Sci
• Course: MACM 101
• Professor: Andrei Bulatov

Document Summary

A congruence of the form ax b (mod m) where m is a positive integer, a and b are integers, and x is a variable, is called a linear congruence. If a is relatively prime with m, then it has the inverse a-1. Then a-1 ax a-1 b (mod m) x a-1 b (mod m) 3-1 3x = 3-1 4(mod 7) x 3-1 4(mod 7) 3 5 = 15 1(mod 7) 3-1 = 5(mod 7) x 5 4(mod 7) 20(mod 7) x 6(mod 7) Solve the linear congruence 3x 4 (mod 7) A linear congruence is similar to a single linear equation. What about systems of equations? (sun tzu"s puzzle, 400 460 bc): There are certain things whose number is unknown. When divided by 3, the remainder is 2; when divided by 5, the remainder is 3; and when divided by 7, the remainder is 2.