Modular Arithmetic

Modular arithmetic is "clock arithmetic." It simplifies number theory by ignoring multiples of a certain number $n$.

Definition

Equivalently, $a$ and $b$ leave the same remainder when divided by $n$.

Arithmetic Operations

If $a\equiv b(\mathrm{mod}n)$ and $c\equiv d(\mathrm{mod}n)$:

1. Addition: $a+c\equiv b+d(\mathrm{mod}n)$.
2. Subtraction: $a-c\equiv b-d(\mathrm{mod}n)$.
3. Multiplication: $ac\equiv bd(\mathrm{mod}n)$.
4. Exponentiation: $a^k\equiv b^k(\mathrm{mod}n)$ (for integer $k\ge 0$).

Residue Classes

The set of integers modulo $n$ is denoted ${\mathbb{Z}}_n$ or $\mathbb{Z}/n\mathbb{Z}$. A complete residue system is $\{0,1,\dots ,n-1\}$.

Practice Problems