Toolkit 47: Modular Arithmetic

Definition

a is congruent to b modulo m if and only if their difference is divisible by m:

a\equiv b\pmod m\iff m\mid(a-b)

Properties

\begin{aligned} 1.\quad & a\equiv a\pmod m \\[10pt] 2.\quad & a\equiv b\pmod m\Rightarrow b\equiv a\pmod m \\[10pt] 3.\quad & a\equiv b\pmod m,\qquad b\equiv c\pmod m\Rightarrow a\equiv c\pmod m \\[10pt] 4.\quad & a\equiv b\pmod m\Rightarrow \begin{cases} a+c\equiv b+c\pmod m\\ a-c\equiv b-c\pmod m\\ ac\equiv bc\pmod m \end{cases} \\[16pt] 5.\quad & a\equiv b\pmod m,\qquad c\equiv d\pmod m\Rightarrow \begin{cases} a+c\equiv b+d\pmod m\\ a-c\equiv b-d\pmod m\\ ac\equiv bd\pmod m \end{cases} \\[16pt] 6.\quad & a\equiv b\pmod m\Rightarrow a^n\equiv b^n\pmod m,\qquad n\in\mathbb Z^+ \\[10pt] 7.\quad & ac\equiv bc\pmod m\iff a\equiv b\pmod{\frac{m}{\gcd(m,c)}} \\[12pt] 8.\quad & a\equiv b\pmod m,\qquad d\mid m\Rightarrow a\equiv b\pmod d \end{aligned}