Clocks, calendars and odd/even all ignore multiples of some fixed number: 15 hours after 11 o'clock is 2 o'clock, because only the remainder mod 12 matters. Gauss turned this into an algebra with one new symbol, and it is the language of the rest of this course.
Definition. Let $n \ge 1$. Integers $a$ and $b$ are congruent mod $n$, written $$a \equiv b \pmod{n},$$ when $n \mid (a - b)$. The number $n$ is the modulus. For example $38 \equiv 3 \pmod{7}$, because $38 - 3 = 35 = 7 \cdot 5$.
Why it works
Congruence mod $n$ is an equivalence relation: $a \equiv a$; if $a \equiv b$ then $b \equiv a$; if $a \equiv b$ and $b \equiv c$ then $a \equiv c$ (add $a - b$ and $b - c$). Its classes, the residue classes, are the $n$ sets of integers with remainder $0, 1, \dots, n - 1$. The least nonnegative residue of $a$ is its remainder, the one representative from $0$ to $n - 1$.
Worked example: Least nonnegative residues
- $38 = 7 \cdot 5 + 3$, so $38 \equiv 3 \pmod{7}$.
- $-3 = 7 \cdot (-1) + 4$, so $-3 \equiv 4 \pmod{7}$.
- Many numbers name the same class: $38 \equiv 3 \equiv 10 \equiv -4 \pmod{7}$.
Answer: $3$ and $4$.
Worked example: Which moduli work?
- We need $n \mid 41 - 17 = 24$.
- The divisors of $24$ above $1$: $2, 3, 4, 6, 8, 12, 24$.
Answer: $n = 2, 3, 4, 6, 8, 12$ or $24$.
Worked example: Odd squares mod 8
- An odd number is $\equiv 1, 3, 5$ or $7 \pmod{8}$.
- $1^{2} = 1$, $3^{2} = 9 \equiv 1$, $5^{2} = 25 \equiv 1$, $7^{2} = 49 \equiv 1 \pmod{8}$.
- So every odd square is $\equiv 1 \pmod{8}$ (squares of congruent numbers are congruent, as the next lesson shows).
Answer: Always $1$.
Common mistake
Key idea