15 251 Great Theoretical Ideas in Computer Science Number Theory and Modular Arithmetic Lecture 13 October 06 2008 p 1 p 1 MAX a b MIN a b a b n m means that m is an integer multiple of n We say that n divides m 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 If a dn r with 0 r n Then r a mod n and d a div n Defn Modular equivalence of integers a and b a b mod n a mod n b mod n n a b Written as a n b and spoken a and b are equivalent modulo n 31 81 mod 2 31 2 81 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 a n b n a b a and b are equivalent modulo n n induces a natural partition of the integers into n classes a and b are said to be in the same residue class or congruence class precisely when a n b a n b n a b a and b are equivalent modulo n Define Residue class i the set of all integers that are congruent to i 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 7 5 2 1 4 7 1 4 1 2 5 8 Fact equivalence mod n implies equivalence mod any divisor of n If x n y and k n Then x k y Example 10 6 16 10 3 16 If x Proof y and k n then x k y n Fundamental lemma of plus minus and times mod n If x y and a n b Then 1 x a n y b 2 x a n y b 3 x a n y b n Proof of 3 xa yb mod n The other two proofs are similar Fundamental lemma of plus minus and times modulo n When doing plus minus and times modulo n I can at any time in the calculation replace a number with a number in the same residue class modulo n Please calculate 249 504 mod 251 when working mod 251 2 2 4 247 A Unique Representation System Modulo n We pick exactly one representative from each residue class We do all our calculations using these representatives Unique representation system modulo 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 modulo 3 Finite set S 0 1 1 and defined on S 0 1 1 0 1 1 0 0 1 1 0 0 0 0 1 1 1 0 1 0 1 1 1 1 0 1 1 0 1 1 Perhaps the most convenient set of representatives The reduced system modulo n 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 Zn 0 1 2 n 1 a n b a b mod n a n b a b mod 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 Zn 0 1 2 n 1 a n b a b mod n a n b a b mod 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 Zn 0 1 2 n 1 a n b a b mod n a n b a b mod n n and n are commutative and associative binary operators from Zn Zn Zn The reduced system modulo 3 Z3 0 1 2 Two binary associative operators on 3 0 1 0 1 2 3 0 0 0 0 0 1 2 1 0 1 1 1 2 0 2 0 2 2 2 0 1 Z3 2 0 2 1 The reduced system modulo 2 Z2 0 1 Two binary associative operators on Z2 2 2 0 1 0 1 0 0 1 0 0 0 1 1 0 1 0 1 The Boolean interpretation of Z2 Z2 0 1 Two binary associative operators on Z2 2 0 1 XOR 2 0 1 AND 0 0 1 0 0 0 1 1 0 1 0 1 The reduced system Z4 0 1 2 3 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 The reduced system 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 4 2 2 3 4 0 1 2 0 2 4 1 3 3 3 4 0 1 2 3 0 3 1 4 2 4 4 0 1 2 3 4 0 4 3 2 1 The reduced system Z6 0 1 2 3 4 5 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 0 1 2 3 4 0 0 0 0 0 0 1 0 1 2 3 4 2 0 2 4 0 2 3 0 4 0 4 2 0 4 5 0 5 4 3 2 5 The reduced system Z6 0 1 2 3 4 5 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 An operator has the permutation property if each row and each column has a permutation of the elements For every n n on Zn has the permutation property 0 1 2 3 4 5 0 0 1 2 3 4 5 1 1 2 3 4 …
View Full Document
Unlocking...