Congruences - Core Definitions

The theory of congruences, introduced by Carl Friedrich Gauss in his groundbreaking 1801 work Disquisitiones Arithmeticae, provides a powerful framework for studying divisibility and remainders. Congruence arithmetic forms the foundation of modern cryptography and coding theory.

DefinitionCongruence Modulo n

Let $n$ be a positive integer. Two integers $a$ and $b$ are said to be congruent modulo $n$ , written: $a \equiv b \pmod{n}$ if $n \mid (a - b)$ , that is, if $a - b = kn$ for some integer $k$ .

The integer $n$ is called the modulus of the congruence.

The notation $a \equiv b \pmod{n}$ should be read as " $a$ is congruent to $b$ modulo $n$ ." This relation captures the idea that $a$ and $b$ leave the same remainder when divided by $n$ .

ExampleBasic Congruences

$17 \equiv 5 \pmod{12}$ because $17 - 5 = 12 = 12 \cdot 1$
$-3 \equiv 7 \pmod{10}$ because $-3 - 7 = -10 = 10 \cdot (-1)$
$100 \equiv 0 \pmod{25}$ because $100 - 0 = 100 = 25 \cdot 4$

Note that $17$ and $5$ both leave remainder $5$ when divided by $12$ , and $-3$ and $7$ both leave remainder $7$ when divided by $10$ .

TheoremProperties of Congruence

Congruence modulo $n$ is an equivalence relation on $\mathbb{Z}$ :

Reflexivity: $a \equiv a \pmod{n}$ for all $a$
Symmetry: If $a \equiv b \pmod{n}$ , then $b \equiv a \pmod{n}$
Transitivity: If $a \equiv b \pmod{n}$ and $b \equiv c \pmod{n}$ , then $a \equiv c \pmod{n}$

Moreover, congruence is compatible with arithmetic operations:

If $a \equiv b \pmod{n}$ and $c \equiv d \pmod{n}$ , then $a + c \equiv b + d \pmod{n}$
If $a \equiv b \pmod{n}$ and $c \equiv d \pmod{n}$ , then $ac \equiv bd \pmod{n}$

These properties allow us to perform arithmetic with congruences much like we do with equations, making congruence arithmetic extremely practical for computation.

DefinitionResidue Classes

The equivalence class of an integer $a$ modulo $n$ is called the residue class of $a$ modulo $n$ : $[a]_n = \{a + kn : k \in \mathbb{Z}\}$

The set of all residue classes modulo $n$ is denoted $\mathbb{Z}/n\mathbb{Z}$ or $\mathbb{Z}_n$ , and contains exactly $n$ elements: $\mathbb{Z}/n\mathbb{Z} = \{[0]_n, [1]_n, [2]_n, \ldots, [n-1]_n\}$

A complete system of residues modulo $n$ is a set containing exactly one representative from each residue class.

ExampleResidue Classes Modulo 5

The residue classes modulo $5$ are:

$[0]_5 = \{\ldots, -10, -5, 0, 5, 10, \ldots\}$
$[1]_5 = \{\ldots, -9, -4, 1, 6, 11, \ldots\}$
$[2]_5 = \{\ldots, -8, -3, 2, 7, 12, \ldots\}$
$[3]_5 = \{\ldots, -7, -2, 3, 8, 13, \ldots\}$
$[4]_5 = \{\ldots, -6, -1, 4, 9, 14, \ldots\}$

The set $\{0, 1, 2, 3, 4\}$ is the standard complete system of residues modulo $5$ , but $\{-2, -1, 0, 1, 2\}$ or $\{1, 2, 3, 4, 5\}$ would work equally well.

The algebraic structure $(\mathbb{Z}/n\mathbb{Z}, +, \cdot)$ forms a commutative ring, which becomes a field precisely when $n$ is prime.