Modular arithmetic a= b mod m iff (a-b)=km+ b for some m Zm the equivalence class under mod m m Canonical form: Zm=10, 1, 2 ,., m-1, we use the positive remainder as the standard representation
Modular Arithmetic • a = b mod m iff (a-b) = km + b for some m • Zm the equivalence class under mod m • [a]m • Canonical form: Zm = {0,1,2,…,m-1}, we use the positive remainder as the standard representation
Modular arithmetic 1=m-1 mod m Z7={0,1,2,34,56} (Zm +, x, 0, 1)defines a ring +× are closed associative and commutative Operation x distributes over -o is the identity for and 1 for x Additive inverse and multiplicative inverse
Modular Arithmetic • -1 = m -1 mod m • Z7 = {0,1,2,3,4,5,6} • (Zm, +, ,0, 1) defines a ring – +, are closed – associative and commutative – Operation distributes over + – 0 is the identity for + and 1 for – Additive inverse and multiplicative inverse
Multiplicative Inverses and Congruence equations When does a number has a multiplicative inverse? When does a congruence equation ax = b mod m has a solution has a unique solution 5X=8mod12=>x=4 3x=8 mod 12==> no solution 3X=9mod12=>xin{3,7,11}
Multiplicative Inverses and Congruence Equations • When does a number has a multiplicative inverse? • When does a congruence equation ax = b mod m – has a solution – has a unique solution • 5x = 8 mod 12 ==> x = 4 • 3x = 8 mod 12 ==> no solution • 3x = 9 mod 12 ==> x in {3,7,11}