## CSE 141: Modular Arithmatic and Congruences

Definition:

1. If $m|a-b$ then $a \equiv b \pmod{m}$.

Where $a$ and $b$ are integers and $m$ is a positive integer.

2. If $a\,\bmod\,m=r$

and $b\,\bmod\,m=r$

then $a \equiv b \pmod{m}$.

Where $a$ and $b$ are integers and $m$ is a positive integer.

3. If $a=b+km$

then, $a \equiv b \pmod{m}$.

Where $a$, $b$ and $k$ are integers and $m$ is a positive integer.

Example:

$5\,\bmod\,7=5$

$12\,\bmod\,7=5$

So $12 \equiv 5 \pmod{7}$

Algebra of Congruence:

If $a \equiv b \pmod{m}$

and $c \equiv d \pmod{m}$

then $a+c \equiv b+d \pmod{m}$

also $ac \equiv bd \pmod{m}$.