slides

Report
CSE 20
DISCRETE MATH
Prof. Shachar Lovett
http://cseweb.ucsd.edu/classes/wi15/cse20-a/
Clicker
frequency:
CA
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 0 2 + 1 2 ?
A.
B.
C.
D.
E.
02
12
21
All integers
Other
Modular addition: examples
• What is 4 7 + 5 7 ?
A.
B.
C.
D.
E.
17
27
72
74
Other
Modular addition: examples
• What is 4 7 + 1 2 ?
A.
B.
C.
D.
E.
57
5 14
72
1 14
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
• 0 2+ 0 2= 0 2
• 0 2+ 1 2= 1 2
• 1 2+ 0 2= 1 2
• 1 2+ 1 2= 0 2
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 ∈ 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
= 0 4; 3
4
∗ 3
4
= 1 4;
• So,  2 +  2  4 can either be 0 4 , 1 4 or 2 4
• 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

similar documents