V Adamchik 1 Modular Arithmetic Victor Adamchik Fall of 2005 Plan 1 Review 2 Applications of Modular Arithmetic 3 Solving Linear Congruences 4 Chinese Remainder Theorem 5 Arithmetic with Large Integers Review Definition a mod n means the remainder when a is divided by n a qn r Definition modulo equivalence a b mod n if and only if n a b We will say that a and b are equivalent modulo n We will also write modulo equivalence as a Theorem n n b is an equivalence relation on the integers An equivalence class consists of those integers which have the same remainder on division by n The equivalence classes are also known as congruence classes modulo n Rather than say the integers a and b are equivalent we say that they are congruent modulo n Definition The set of all integers congruent to a modulo n is called the residue class a Example Residue classes mod 3 V Adamchik 21 127 Concepts of Mathematics 0 6 3 0 3 6 1 5 2 1 4 7 2 4 1 2 5 8 Definition The set of residue classes is denoted by Zn Zn 0 1 2 n 1 Theorem arithmetic on Zn When we are doing or modulo n we can replace a number by another number in the same residue class Example Compute 414 463 mod 413 1 50 50 Note cancelation property Though it seems that arithmetic on Zn is the same as on Z do not be deceived The product of two non zero elements of Zn can sometimes be 0 Question Is the following implication correct xa Only if GCD x n n xb a n b 1 Proof xa n xb n xa xb n x a b n a Definition Zn x Zn GCD x n Example Z0 0 1 2 3 4 5 Z6 1 5 1 b a n b V Adamchik 3 Advantage of Zn is that it has a cancelation property Definition Euler s phi function or totient function is the size of Zn n n is the number of integers 1 k Zn n coprime to n Example 12 It s easy to see that if p is prime then 1 5 7 11 p p Note A number s multiplicative inverse x 1 4 1 More on this function later defined by x x 1 1 is another difference between Zn and Z In Z only two elements have inverses 1 and 1 We have proved that if p is prime then each element in Z p has an inverse We say that Z p is a finite field a set in which we can The prove is based on the following theorem Theorem Ferma s little theorem If p is prime and p 1 ap p a then 1 According to this theorem the inverse is defined by assuming p is prime a 1 ap 2 Applications of Modular Arithmetic Problem 1 How do we efficiently store people s records If we use Social Security number as the key we will have to deal with an array of size 1010 The solution hashing Store records in the table at index h k defined by hk k mod N Here h is a hash function and N is an array size Regardless of chosen N collisions might happen h k1 h k2 V Adamchik 21 127 Concepts of Mathematics You will deal with collisions in 15 211 Problem 2 How do we generate a random number There is nothing random about random or rand function The standard technique is to create a pseudorandom sequence The most commonly used procedure for generating pseudorandom numbers is the linear congruential method Lehmer 1949 We generate a sequence of pseudorandom numbers xk by successively using the congruence xn with appropriate values of 0 a 1 a xn x0 m m 0 b b mod m n is the seed m m 0 0 and GCD b m 1 For example xn 7 xn 4 mod 9 n x0 3 1 0 This generates the following sequence x1 7 x0 4 7 3 4 25 7 mod 9 x2 7 x1 4 7 7 4 53 8 mod 9 x3 7 x2 4 7 8 4 60 6 mod 9 and so on This recurrence is eventually periodic So it is desirable to use a recurence with the long period Problem 3 ISBN numbers for published books The ISBN number for our textbook is 0 13 184 868 2 The information is decoded in the first 9 digits The last digit is for parity check 1 a1 2 a2 9 a9 a10 mod 11 Applying this to our textbook 1 0 2 1 3 3 4 1 5 8 6 4 7 8 8 6 9 8 255 2 mod 11 V Adamchik 5 The sum of 9 digits is 255 and it equals to the last digit mod 11 Problem 4 The Gauss Easter formula The church set the Easter on first Sunday after the first full moon in spring The Easter sunday always moves in the period of 22nd March until 25th April F Gauss developed the exact formula to calculate the date of Easter Here is its short version a b c d e year year year 19 a 2b mod 11 mod 4 mod 7 M mod 30 4 c 6 d N mod 7 where constants M and N are M N 24 5 valid throughout the period between 1900 and 2099 years Then Easter falls on 22 or d e d e March 9 April year 2006 a Mod year 19 b Mod year 4 c M 24 n 5 1900 2099 d Mod 19 a M 30 e Mod 2 b 4 c 6 d n 7 22 d e march d e 9 april Mod year 7 47 16 In 2006 the catholic church will celebrate Easter on April 16 Dates are according the Gregorian calendar Here i sthe full version of the algorithm see http www smart net mmontes nature1876 html published in Nature 1876 April 20 vol 13 p 487 V Adamchik 21 127 Concepts of Mathematics year 2006 a Mod year 19 b IntegerPart year 100 c Mod year 100 d IntegerPart b 4 e Mod b 4 f IntegerPart b 8 25 g IntegerPart b f 1 3 h Mod 19 a b d g 15 30 i IntegerPart c 4 k Mod c 4 l Mod 32 2 e 2 i h k 7 m IntegerPart a 11 h 22 l 451 EasterMonth IntegerPart h l 7 m 114 p Mod h l 7 m 114 31 EasterDate p 1 EasterDate EasterMonth 31 3 March 4 April 16 4 Solving Linear Congruences Definition A relation of the form a x b mod n is called a linear congruence We will also write this as a x n b How many solutions does it have It s clear that if x0 is a solution then every element from a congruent class is also a solution Example x 3 mod 4 Here are solutions 1 3 7 10 Therefore uniqueness …