Understanding Modular Arithmetic: Equivalence Relations and Examples
Explore the concept of modular arithmetic, equivalence relations, and examples related to it. Learn about the definitions, properties, and applications of modular arithmetic in discrete math. Understand how to determine equivalence classes and solve problems using modular arithmetic.
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
Clicker frequency: CA CSE 20 DISCRETE MATH Prof. Shachar Lovett http://cseweb.ucsd.edu/classes/wi15/cse20-a/
Todays topics Modular arithmetic Section 6.2 in Jenkyns, Stephenson
Recall: equivalence relations Saw two equivalent definitions xRy is an equivalence relation if Symmetric: ?,?, ??? ??? Reflexive: ?, ??? Transitive: ?,?,?, ??? ??? ??? Equivalently: there is a partition of the universe to equivalence classes, and xRy iff x,y are in the same class Can be phrased as: ?,?????:? ? such that ??? ????? ? = ?????(?)
Today: modular arithmetic A very important (and very useful) example of an equivalence relation Recall our example of {even,odd} classes: ??? 2| ? ? x,y are both even, or both odd Modular arithmetic generalizes this from 2 to any divisor
Modular arithmetic: definition Fix ? 2 Define a relation: integers x,y are equivalent modulo m, if ? ??? ? = ? ??? ? Equivalently, ?|? ? Defines a partition of Z to m equivalence classes ??= {? ?:? ??? ? = ?} where ? {0,1, ,? 1}
Modular arithmetic: examples ??= {? ?:? ??? ? = ?} What is [0]2? A. All integers B. 0 C. Even numbers D. Odd numbers E. Other
Modular arithmetic: examples ??= {? ?:? ??? ? = ?} What is [1]2? A. All integers B. 1 C. Even numbers D. Odd numbers E. Other
Modular arithmetic: examples ??= {? ?:? ??? ? = ?} What is [0]3? A. All integers B. All integers divisible by 3 C. All integers whose value mod 3 is equal to 1 D. All integers whose value mod 3 is equal to 2 E. Other
Modular arithmetic: examples ??= {? ?:? ??? ? = ?} What is [1]3? A. All integers B. All integers divisible by 3 C. All integers whose value mod 3 is equal to 1 D. All integers whose value mod 3 is equal to 2 E. Other
Modular arithmetic: examples ??= {? ?:? ??? ? = ?} What is [4]3? A. All integers B. All integers divisible by 3 C. All integers whose value mod 3 is equal to 1 D. All integers whose value mod 3 is equal to 2 E. Other
Modular arithmetic: notation Notation: to say that ? ??, we typically write ? ? ??? ? More generally, for any two integers x,y we can write ? ? ??? ? which means that x,y belong to the same equivalence class modulo m, which means ?|? ?.
Modular addition and multiplication Why is modular arithmetic so important? Because we can operate directly on the equivalence classes, adding and multiplying them (for a fixed modulus m) Definition: for any fixed ? 2, ??+ ??= And ?? ??= ? + ? ??? ?? ? ? ??? ?? Theorem: this is well defined What does this even mean???
Modular addition Theorem: ??+ ??= ? + ? ??? ?? Interpretation: if we take any ? ??, and any ? ??, then it is always true that ? + ? ? + ? ??? ?? Equivalently: ? ??? ? + ? ??? ? ??? ? = ? + ? ??? ?
Modular addition: proof Theorem: ??+ ??= ? + ? ??? ?? Proof: we need to show ? ??,? ??, ? + ? ??? ? = ? + ? ??? ? Let ? = ?? + ?,? = ?? + ? and ? + ? = ?? + ?, with ?,?,? {0, ,? 1}. Then: ? + ? = ? + ? ? + ? + ? = ? + ? + ? ? + ? So ? + ? ??, and also a + ? ??. QED.
Modular addition: examples What is 02+ 12? 02 12 21 A. B. C. D. All integers E. Other
Modular addition: examples What is 47+ 57? 17 27 72 74 A. B. C. D. E. Other
Modular addition: examples What is 47+ 12? 57 514 72 114 A. B. C. D. E. Other
Be careful! We can only add ??+ ?? if ? = ?. Otherwise, this is not defined!!! Also: in the special case of ? = 2, addition modulo 2 corresponds to XOR 02+ 02= 02 02+ 12= 12 12+ 02= 12 12+ 12= 02
Modular multiplication Theorem: ?? ??= ? ? ??? ??
Modular multiplication: proof Theorem: ?? ??= ? ? ??? ?? Proof: we need to show ? ??,? ??, ? ? ??? ? = ? ? ??? ? Let ? = ?? + ?,? = ?? + ? and ? ? = ?? + ?, with ?,?,? {0, ,? 1}. Then: ? ? = ?? + ? ?? + ? = ???2+ ??? + ??? + ?? = ???2+ ??? + ??? + ?? + ? = ? ??? + ?? + ?? + ? + ? So ? ? ??, and also a ? ??. QED.
Applications of modular arithmetic For a fixed ? 2, we can add, multiply and take modulo m, and the value (modulo m) 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 ?,? ? such that ?2+ ?2= 1234567 Hint: use values modulo 4
Applications of modular arithmetic Theorem: there are no ?,? ? such that ?2+ ?2= 1234567 Hint: use values modulo 4 Solution: for any ? ?, ?2 04 or ?2 14. There are 4 cases to check: 04 04= 04; 14 14= 14; 24 24= 04; 34 34= 14; So, ?2+ ?2 ?????? 4 can either be 04, 14 or 24 But 1234567 3 (??? 4), so they cannot be equal!
Applications of modular arithmetic Cryptography Your online transactions are encrypted, based on modular arithmetic RSA public key crpytosystem: Very large m, product of two large primes m=p*q Message: ? {0,1, ,? 1} Encryption: ?? ??? ? Security is based on the assumption that factorization is hard
