Discrete Mathematics for Computer Science with Prof. Shachar Lovett
Explore the world of modular arithmetic in Discrete Mathematics for Computer Science with Prof. Shachar Lovett. Learn about residue classes, equivalence relations, and modular addition, all essential topics for computer science students.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
CSE 20: Discrete Mathematics for Computer Science Prof. Shachar Lovett
2 Today s Topics: 1. Modular arithmetics
3 1. Modular Arithmetic
4 Modular arithmetics Let ? 2 be an integer MODULO n is an equivalence relation defines as follows: xRy if n|(x-y) eg n divides x-y We write this as x y (mod n)
5 Residue classes Remember that equivalence relations = partition of universe to equivalence classes Even = [0 mod 2] = { ,-4,-2,0,0,2,4, } Odd = [1 mod 2] = { ,-3,-1,1,3, } Partition by value modulo 2
6 Residue classes Similarly, there are 3 residue classes modulo 3 [0 mod 3] = {x: x=3a} = { ,-6,-3,0,3,6, } [1 mod 3] = {x: x=3a+1} = { ,-5,-2,1,4,7, } [2 mod 3] = {x: x=3a+2} = { ,-4,-1,2,5,8, } Similarly, modulo n defines n residue classes. For x Z, we denote by [x mod n] its residue class.
7 Modular addition We can add residue classes. Fix n. [x mod n]+[y mod n]=[x+y mod n] This is well defined. What does that mean? A. For any x,y, the sum x+y is defined B. The definition of sum does not depend on choice of representatives C. There is a way to obtain all residue classes D. I don t know
8 Modular addition Residue classes mod 5 0 mod 5 4 mod 5 1 mod 5 3 mod 5 2 mod 5
9 Modular addition Residue classes mod 5 [x mod 5]+[1 mod 5]=[x+1 mod 5] 0 mod 5 4 mod 5 1 mod 5 3 mod 5 2 mod 5
10 Modular addition [x mod n]+[y mod n]=[x+y mod n] Theorem: this is well defined This means: if x,x Z are such that x mod n=x mod n; and y,y Z are such that y mod n=y mod n. Then (x+y) mod n = (x +y ) mod n. So, the definition of addition does not depend on the chosen representatives for each residue class
11 Modular addition [x mod n]+[y mod n]=[x+y mod n] Theorem: this is well defined Proof (direct proof): If x mod n=x mod n then x =x+na for a Z If y mod n=y mod n then y =y+nb for b Z Then (x +y )=(x+y)+n(a+b) So [x +y mod n]=[x+y mod n] QED
12 Modular addition [2 mod 5]+[4 mod 5]= A. 0 B. [2 mod 5] C. [1 mod 5] D. [1 mod 4] E. None/other/more than one
13 Modular multiplication [x mod n]*[y mod n]=[x*y mod n] Theorem: this is well defined Proof (direct proof): If x mod n=x mod n then x =x+na for a Z If y mod n=y mod n then y =y+nb for b Z Then (x *y )=(x*y)+n(ay+bx+nab) So [x *y mod n]=[x*y mod n] QED
14 Modular multiplication [2 mod 5]*[4 mod 5]= A. [1 mod 5] B. [2 mod 5] C. [3 mod 5] D. [4 mod 5] E. None/other/more than one
15 Modular multiplication [2 mod 5]*[4 mod 7]= A. [1 mod 5] B. [2 mod 7] C. [3 mod 35] D. [8 mod 35] E. None/other/more than one
16 Modular multiplication X={0,1,2,3,4} Define: xRy if [2x mod 5]=[y mod 5] Is R A. Symmetric B. Reflexive C. Transitive D. More than one E. None
17 The ring Zn Define Zn={[0 mod n],[1 mod n], ,[n-1 mod n]} The set of all residue classes modulo n We defined addition and multiplication on Zn You can check: they obey all the usual definitions of addition and multiplication (abbrv. [x]=[x mod n]) [x]+[y]=[y]+[x]; [x]*[y]=[y]*[x] [x]*([y]+[z])=[x]*[y]+[x]*[z] [x]+[0]=[x]; [x]*[1]=[x] Sets which support addition and multiplication are called rings
18 The ring Zn If n is not prime, weird stuff can happen Example: [2 mod 6] * [3 mod 6] = A. [0 mod 6] B. [2 mod 6] C. [3 mod 6] D. [5 mod 6] E. None/other/more than one
19 The ring Zn If n is not prime, weird stuff can happen Example: [2 mod 6] * [3 mod 6] = [0 mod 6] That is, we multiplied two nonzero elements, and got zero as a result (these are called zero divisors)
Applications of modular arithmetic For a fixed n 2, we can add, multiply and take modulo m, and the value (modulo n) will stay invariant This is very useful; many algorithmic applications Example 1: verifying calculations Prove that 12294793 2329373 92739273 Hint: use values modulo 10
Applications of modular arithmetic Example 1: prove that 12294793 2329373 92739273 Solution: compute values modulo 10 12294793 3 ??? 10 2329373 3 ??? 10 92739273 3 ??? 10 But 3 3 9 ??? 10 , so the equation cannot be correct
Applications of modular arithmetic Example 2: number theory Theorem: there are no integer solutions to the equation ?2+ ?2= 1234567 Hint: use values modulo 4
Applications of modular arithmetic Theorem: there are no integer solutions to the equation ?2+ ?2= 1234567 Hint: use values modulo 4 Solution: for any ? ?, ?2= 0 ??? 4 or ?2= 1 ??? 4 . There are 4 cases to check: 0 ??? 4 0 ??? 4 = 0 ??? 4 1 ??? 4 1 ??? 4 = 1 ??? 4 2 ??? 4 2 ??? 4 = 4 ??? 4 = (0 ??? 4) 3 ??? 4 3 ??? 4 = 9 ??? 4 = (1 ??? 4) So, ?2+ ?2 ?????? 4 can only be 0,1 or 2 But 1234567 3 (??? 4), so they cannot be equal!
Applications of modular arithmetic Example 3: Cryptography Your online transactions are encrypted, based on modular arithmetic RSA public key crypto-system: Very large n, product of two large primes n=p*q Message: ? {0,1, ,? 1} Encryption: ?? ??? ? Security is based on the assumption that factorization is hard
