Modular Arithmetic

Congruence Modulo $n$

Definition

For integers $a, b$ and a positive integer $n \geq 1$, we say $a$ is congruent to $b$ modulo $n$, written $a \equiv b \pmod{n}$, if and only if:

$n \mid (a - b)$

Equivalently, $a \equiv b \pmod{n}$ iff $a$ and $b$ have the same remainder when divided by $n$.

Examples

• $17 \equiv 5 \pmod{12}$ since $17 - 5 = 12$ and $12 \mid 12$
• $23 \equiv 2 \pmod{7}$ since $23 - 2 = 21$ and $7 \mid 21$
• $-5 \equiv 3 \pmod{8}$ since $-5 - 3 = -8$ and $8 \mid -8$

Congruence is an Equivalence Relation

Reflexivity

$a \equiv a \pmod{n}$

Since $n \mid (a - a) = 0$ for all $n$.

Symmetry

$a \equiv b \pmod{n} \Rightarrow b \equiv a \pmod{n}$

Since $n \mid (a - b)$ implies $n \mid (b - a)$.

Transitivity

$a \equiv b \pmod{n} \land b \equiv c \pmod{n} \Rightarrow a \equiv c \pmod{n}$

Proof: $n \mid (a - b)$ and $n \mid (b - c)$ implies $n \mid [(a-b) + (b-c)] = a - c$.

Congruence Classes

The congruence class of $a$ modulo $n$ is:

$[a]_n = \{b \in \mathbb{Z} : a \equiv b \pmod{n}\} = \{a + kn : k \in \mathbb{Z}\}$

Examples

• $[0]_3 = \{\ldots, -6, -3, 0, 3, 6, 9, \ldots\}$
• $[1]_3 = \{\ldots, -5, -2, 1, 4, 7, 10, \ldots\}$
• $[2]_3 = \{\ldots, -4, -1, 2, 5, 8, 11, \ldots\}$

Number of Classes

There are exactly $n$ congruence classes modulo $n$: $[0]_n, [1]_n, \ldots, [n-1]_n$.

The standard representatives are $\mathbb{Z}_n = \{0, 1, 2, \ldots, n-1\}$.

Arithmetic Operations on Congruences

Addition

If $a \equiv b \pmod{n}$ and $c \equiv d \pmod{n}$, then:

$a + c \equiv b + d \pmod{n}$

Multiplication

If $a \equiv b \pmod{n}$ and $c \equiv d \pmod{n}$, then:

$ac \equiv bd \pmod{n}$

Powers

If $a \equiv b \pmod{n}$, then for any $k \geq 0$:

$a^k \equiv b^k \pmod{n}$

Proof (Multiplication)

Given $a \equiv b \pmod{n}$ and $c \equiv d \pmod{n}$:

$ac - bd = ac - bc + bc - bd = c(a - b) + b(c - d)$

Since $n \mid (a - b)$ and $n \mid (c - d)$, we have $n \mid [c(a-b) + b(c-d)] = ac - bd$.

Thus $ac \equiv bd \pmod{n}$.

Common Pitfall: Cancellation

The Problem

$ac \equiv bc \pmod{n} \not\Rightarrow a \equiv b \pmod{n}$

Counterexample

$2 \cdot 3 \equiv 2 \cdot 0 \pmod{6}$ but $3 \not\equiv 0 \pmod{6}$.

When Does Cancellation Work?

If $\gcd(c, n) = 1$ and $ac \equiv bc \pmod{n}$, then $a \equiv b \pmod{n}$.

Proof: $ac \equiv bc \pmod{n}$ means $n \mid c(a - b)$.

Since $\gcd(c, n) = 1$, Euclid’s lemma gives $n \mid (a - b)$.

Thus $a \equiv b \pmod{n}$.

Divisibility Tests

Test for 2

$|\overline{a_k a_{k-1} \ldots a_1 a_0}|$ is divisible by 2 iff $a_0$ (the last digit) is even.

Reason: $10 \equiv 0 \pmod{2}$, so $a_k \cdot 10^k + \cdots + a_1 \cdot 10 + a_0 \equiv a_0 \pmod{2}$.

Test for 3

A number is divisible by 3 iff the sum of its digits is divisible by 3.

Reason: $10 \equiv 1 \pmod{3}$, so $a_k \cdot 10^k + \cdots + a_1 \cdot 10 + a_0 \equiv a_k + \cdots + a_0 \pmod{3}$.

Test for 9

A number is divisible by 9 iff the sum of its digits is divisible by 9.

Reason: $10 \equiv 1 \pmod{9}$.

Test for 11

A number is divisible by 11 iff the alternating sum of digits $(a_0 - a_1 + a_2 - \cdots)$ is divisible by 11.

Reason: $10 \equiv -1 \pmod{11}$.

---

Summary

• $a \equiv b \pmod{n}$ iff $n \mid (a - b)$
• Congruence is an equivalence relation
• Congruences preserve addition and multiplication
• Cancellation requires $\gcd(c, n) = 1$
• Divisibility tests use modular arithmetic