MATH2020 (Lec 07) - Modular Arithmetic

Modular Arithmetic

Definition 1

• $a,b\in Z,m\in N+$
• $a$ and $b$ are congruent modulo $m$ or $a\equiv b(modm)$ (a congruence) if they leave the same remainder when divided by m (its modulus)
• $a\equiv b(modm)$ if the difference between a and b is a multiple of m → $m|(a-b)$ or $a-b=km$
• a and b not congruent modulo m, we write $a\not\equiv b(\text{mod}m)$

Theorem 2

• $a$ and $b$ are int, m is positive int then $a\equiv b(modm)$ if and only if $(amodm)=(bmodm)$.

Theorem 3

• a and b are congruent modulo int m ⇐> there is int k, that $a=b+km$

Theorem 4: the congruent modulo of 2 products & sums

• if $a\equiv b(modm)$, and $c\equiv d(modm)$, then $a+c\equiv b+d(modm)$ $ac\equiv bd(modm)$

Corollary 5

• m is positive int, a and b are int $(a+b)\mathrm{mod}m=((a\mathrm{mod}m)+(b\mathrm{mod}m))\mathrm{mod}m$ $ab\mathrm{mod}m=((a\mathrm{mod}m)(b\mathrm{mod}m))\mathrm{mod}m$ $a^n\mathrm{mod}m=(a\mathrm{mod}m{)}^n\mathrm{mod}m$
• hard parts:
  • -1 (mod 10) = 9, means adding 9 more to its positive get 10
• how to imagine modulo of negative numbers
  • imagine number line contains only from 0 to 9, and loop back. After 9, we go back to 0. If we start at 0 and move 1 step left (which is -1), we would land on 9 ⇒ $-1mod10=9$

Definition 6: addition and multiplication modulo m

• ${\mathbb{Z}}_m$ is set {0, 1, …, m - 1}. $a{+}_{m}b=(a+b)modm$ $a{\cdot }_{m}b=(a\cdot b)modm$
• this is arithmetic modulo m

Properties of ordinary addition / multiplication of integers

• Closure
• Associativity
• Commutativity
• Identity element
• Additive inverses

Note on modular arithmetic

• a set ${\mathbb{Z}}_m$ with both mod addition or multiplication is commutative ring

Application of of Modular Arithmetic - Hashing

• hashing: $h(k)=kmodN$
• Pseudorandom sequences: use the linear congruential generator (LCG) to generate
  • choose 4 int: modulus m, multiplier a, increment c, seed $x_0$, $2\le a<m$, $0\le c<m$, $0\le x_0<m$
  • $x_0=randomseed$
  • $x_i=(a\cdot x_{i-1}+c)\mathrm{mod}m$