Slide 1Number Theory and Modular ArithmeticSlide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36What’s the pattern?Slide 38Slide 39Slide 40Slide 41Slide 42Slide 43Slide 44Slide 45Slide 46Slide 47Slide 48Slide 49Slide 50Slide 51Slide 52Slide 53Slide 54Slide 55Slide 56Slide 57Slide 58Slide 59Slide 60Slide 61Slide 62Slide 63Finally, a puzzle…why?Slide 66Slide 67Diophantine equationsNew bottles of water puzzleInvariantGeneralized bottles of waterRecall thatSlide 7315-251Great Theoretical Ideas in Computer ScienceLecture 13 (February 24, 2009)Number Theory and Modular Arithmeticp-1p1Greatest 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.You can useMAX(a,b) + MIN(a,b) = a+bto prove the above fact…Fact:GCD(x,y) × LCM(x,y) = x × y(a mod n) means the remainder when a is divided by n. a mod n = ra = dn + r for some integer dDefinition: Modular equivalencea b [mod n] (a mod n) = (b mod n) n | (a-b)Written as a n b, and spoken“a and b are equivalent or congruent modulo n”31 81 [mod 2]31 2 8131 80 [mod 7]31 7 80n is an equivalence relationIn other words, it isReflexive: a n aSymmetric: (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, ..}[7] = { …, -5, -2, 1, 4, 7, ..}[-1] = { …, -4, -1, 2, 5, 8, ..}= [0]= [1]= [2]Why do we care about these residue classes?Because we can replace any member of a residue class with another memberwhen doing addition or multiplication mod nand the answer will not changeTo calculate: 249 * 504 mod 251just do -2 * 2 = -4 = 247Fundamental lemma of plus and times mod n:If (x n y) and (a n b). Then1) x + a n y + b2) x * a n y * bProof of 2: xa = yb (mod n)(The other proof is similar…)Another Simple Fact: If (x n y) and (k|n), then: x k yExample: 10 6 16 10 3 16 Proof: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-1Unique representation system mod 3Finite set S = {0, 1, 2}+ and * defined on S:+ 0 1 20 0 1 21 1 2 02 2 0 1* 0 1 20 0 0 01 0 1 22 0 2 1Unique representation system mod 4Finite set S = {0, 1, 2, 3}+ and * defined on S:+ 0 1 2 30 0 1 2 31 1 2 3 02 2 3 0 13 3 0 1 2* 0 1 2 30 0 0 0 01 0 1 2 32 0 2 0 23 0 3 2 1NotationDefine operations +n and *n:a +n b = (a + b mod n)a *n b = (a * b mod n)Zn = {0, 1, 2, …, n-1}[“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 Some properties of the operation +nSimilar properties also hold for *nUnique representation system mod 3Finite set S = {0, 1, 2}+ and * defined on S:+ 0 1 20 0 1 21 1 2 02 2 0 1* 0 1 20 0 0 01 0 1 22 0 2 1Unique representation system mod 3Finite set Z3 = {0, 1, 2}two associative, commutative operators on Z3Unique representation system mod 3Finite set Z3 = {0, 1, 2}two associative, commutative operators on Z3+ 0 1 20 0 1 21 1 2 02 2 0 1* 0 1 20 0 0 01 0 1 22 0 2 1Unique representation system mod 2Finite set Z2 = {0, 1}two associative, commutative operators on Z2+20 10 0 11 1 0*20 10 0 01 0 1XORANDZ5 = {0,1,2,3,4}+ 0 1 2 3 40 0 1 2 3 41 1 2 3 4 02 2 3 4 0 13 3 4 0 1 24 4 0 1 2 3* 0 1 2 3 40 0 0 0 0 01 0 1 2 32 03 0 3 1 44 0 4 3 2Z6 = {0,1,2,3,4,5}+ 0 1 2 3 4 50 0 1 2 3 4 51 1 2 3 4 5 02 2 3 4 5 0 13 3 4 5 0 1 24 4 5 0 1 2 35 5 0 1 2 3 4* 0 1 2 3 4 50 0 0 0 0 01 0 1 2 3 42 0 2 4 0 23 04 0 4 2 0 45 0 5 4 3 2For addition tables, rows and columnsalways are a permutation of Zn+ 0 1 2 3 4 50 0 1 2 3 4 51 1 2 3 4 5 02 2 3 4 5 0 13 3 4 5 0 1 24 4 5 0 1 2 35 5 0 1 2 3 4+ 0 1 2 3 40 0 1 2 3 41 1 2 3 4 02 2 3 4 0 13 3 4 0 1 24 4 0 1 2 3For multiplication, some rows and columnsare permutation of Zn, while others aren’t…* 0 1 2 3 40 0 0 0 0 01 0 1 2 3 42 0 2 4 1 33 0 3 1 4 24 0 4 3 2 1* 0 1 2 3 4 50 0 0 0 0 0 01 0 1 2 3 4 52 0 2 4 0 2 43 0 3 0 3 0 34 0 4 2 0 4 25 0 5 4 3 2 1what’s happening here?For addition, the permutation propertymeans you can solve, say,+ 0 1 2 3 4 50 0 1 2 3 4 51 1 2 3 4 5 02 2 3 4 5 0 13 3 4 5 0 1 24 4 5 0 1 2 35 5 0 1 2 3 44 + ___ = 1 (mod 6)Subtraction mod n is well-definedEach row has a 0,hence –a is that elementsuch that a + (-a) = 0 a – b = a + (-b)4 + ___ = x (mod 6) for any x in Z6For multiplication, if a row has a permutationyou can solve, say,5 * ___ = 4 (mod 6)* 0 1 2 3 4 50 0 0 0 0 0 01 0 1 2 3 4 52 0 2 4 0 2 43 0 3 0 3 0 34 0 4 2 0 4 25 0 5 4 3 2 1or, 5 * ___ = 1 (mod 6)But if the row does not …
View Full Document