15 251 Great Theoretical Ideas in Computer Science Number Theory and Modular Arithmetic Lecture 13 February 24 2009 p 1 p 1 Greatest Common Divisor GCD x y greatest k 1 s t k x and k y Least Common Multiple LCM x y smallest k 1 s t x k and y k Fact GCD x y LCM x y x y You can use MAX a b MIN a b a b to prove the above fact a mod n means the remainder when a is divided by n a mod n r a dn r for some integer d Definition Modular equivalence a b mod n a mod n b mod n n a b 31 81 mod 2 31 2 81 31 80 mod 7 31 7 80 Written as a n b and spoken a and b are equivalent or congruent modulo n n is an equivalence relation In other words it is Reflexive a n a Symmetric a n b b n a Transitive a n b and b n c a n c n induces a natural partition of the integers into n residue classes residue what left over remainder Define residue class k the set of all integers that are congruent to k modulo n Residue Classes Mod 3 0 6 3 0 3 6 1 5 2 1 4 7 2 4 1 2 5 8 6 6 3 0 3 6 0 7 5 2 1 4 7 1 1 4 1 2 5 8 2 Why do we care about these residue classes Because we can replace any member of a residue class with another member when doing addition or multiplication mod n and the answer will not change To calculate 249 504 mod 251 just do 2 2 4 247 Fundamental lemma of plus and times mod n If x n y and a n b Then 1 x a n y b 2 x a n y b Proof of 2 xa yb mod n The other proof is similar Another Simple Fact If x n y and k n then x k y Example 10 Proof 6 16 10 3 16 A Unique Representation System Modulo n We pick one representative from each residue class and do all our calculations using these representatives Unsurprisingly we use 0 1 2 n 1 Unique representation system mod 3 Finite set S 0 1 2 and defined on S 0 1 2 0 0 1 2 1 1 2 0 2 2 0 1 0 1 2 0 0 0 0 1 0 1 2 2 0 2 1 Unique representation system mod 4 Finite set S 0 1 2 3 and defined on S 0 1 2 3 0 1 2 3 0 0 1 2 3 0 0 0 0 0 1 1 2 3 0 1 0 1 2 3 2 2 3 0 1 2 0 2 0 2 3 3 0 1 2 3 0 3 2 1 Notation Zn 0 1 2 n 1 Define operations n and n a n b a b mod n a n b a b mod n Some properties of the operation n Closed x y Zn x n y Zn Associative x y z Zn x n y n z x n y n z Commutative x y Zn x n y y n x Similar properties also hold for n Unique representation system mod 3 Finite set S 0 1 2 and defined on S 0 1 2 0 0 1 2 1 1 2 0 2 2 0 1 0 1 2 0 0 0 0 1 0 1 2 2 0 2 1 Unique representation system mod 3 Finite set Z3 0 1 2 two associative commutative operators on Z3 Unique representation system mod 3 Finite set Z3 0 1 2 two associative commutative operators on Z3 0 1 2 0 0 1 2 1 1 2 0 2 2 0 1 0 1 2 0 0 0 0 1 0 1 2 2 0 2 1 Unique representation system mod 2 Finite set Z2 0 1 two associative commutative operators on Z2 2 0 1 0 0 1 1 1 0 XOR 2 0 1 0 0 0 1 0 1 AND Z5 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 0 1 2 3 4 0 0 0 0 0 0 1 1 2 3 4 0 1 0 1 2 3 2 2 3 4 0 1 2 0 3 3 4 0 1 2 3 0 3 1 4 4 4 0 1 2 3 4 0 4 3 2 Z6 0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 0 0 1 2 3 4 5 0 0 0 0 0 0 1 1 2 3 4 5 0 1 0 1 2 3 4 2 2 3 4 5 0 1 2 0 2 4 0 2 3 3 4 5 0 1 2 3 0 4 4 5 0 1 2 3 4 0 4 2 0 4 5 5 0 1 2 3 4 5 0 5 4 3 2 5 For addition tables rows and columns always are a permutation of Zn 0 1 2 3 4 0 1 2 3 4 5 0 0 1 2 3 4 0 0 1 2 3 4 5 1 1 2 3 4 0 1 1 2 3 4 5 0 2 2 3 4 0 1 3 3 4 0 1 2 2 2 3 4 5 0 1 4 4 0 1 2 3 3 3 4 5 0 1 2 4 4 5 0 1 2 3 5 5 0 1 2 3 4 For multiplication some rows and columns are permutation of Zn while others aren t 0 1 2 3 4 5 0 0 0 0 0 0 0 4 1 0 1 2 3 4 5 1 3 2 0 2 4 0 2 4 1 4 2 3 0 3 0 3 0 3 3 2 1 4 0 4 2 0 4 2 5 0 5 4 3 2 1 0 1 2 3 4 0 0 0 0 0 0 1 0 1 2 3 2 0 2 4 3 0 3 4 0 4 what s happening here For addition the permutation property means you can solve say 4 1 mod 6 4 x mod 6 for any x in Z6 Subtraction mod n is well defined Each row has a 0 hence a is that element such that a a 0 a b a b 0 1 2 3 4 5 0 0 1 2 3 4 5 1 1 2 3 4 5 0 2 2 3 4 5 0 1 3 3 4 5 0 1 2 4 4 5 0 1 2 3 5 5 0 1 2 3 4 For multiplication if a row has a permutation you can solve say 5 4 mod 6 or 5 1 mod 6 0 1 2 3 4 …
View Full Document
Unlocking...