# Congruence Relations

## Motivation

Ordinary equality compares integers exactly. In many arithmetic problems, however, only the remainder after division matters.

For example, the integers

$$
17
\quad\text{and}\quad
5
$$

leave the same remainder when divided by $12$:

$$
17=12\cdot1+5,
\qquad
5=12\cdot0+5.
$$

From the viewpoint of remainders modulo $12$, these integers behave identically.

This observation leads to the notion of congruence.

## Definition of Congruence

Let $a,b\in\mathbb{Z}$, and let $n\in\mathbb{N}$.

We say that $a$ is congruent to $b$ modulo $n$ if

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

This is written

$$
a\equiv b\pmod n.
$$

Thus two integers are congruent modulo $n$ exactly when their difference is divisible by $n$.

For example,

$$
17\equiv5\pmod{12},
$$

because

$$
17-5=12
$$

and

$$
12\mid12.
$$

Similarly,

$$
29\equiv1\pmod7,
$$

since

$$
29-1=28
$$

and

$$
7\mid28.
$$

## Congruence and Remainders

Two integers are congruent modulo $n$ if and only if they leave the same remainder upon division by $n$.

For example,

$$
23\equiv8\pmod5
$$

because both integers leave remainder $3$ when divided by $5$:

$$
23=5\cdot4+3,
\qquad
8=5\cdot1+3.
$$

This interpretation makes congruence arithmetic intuitive. Modulo $n$, integers are grouped according to their remainders.

## Examples

### Modulo $2$

Every integer is congruent either to $0$ or to $1$ modulo $2$.

Even integers satisfy

$$
a\equiv0\pmod2,
$$

while odd integers satisfy

$$
a\equiv1\pmod2.
$$

Thus parity is congruence modulo $2$.

### Modulo $10$

Two integers are congruent modulo $10$ exactly when they have the same last decimal digit.

For example,

$$
137\equiv7\pmod{10}.
$$

Similarly,

$$
254\equiv4\pmod{10}.
$$

This explains why divisibility tests often depend only on final digits.

## Congruence as an Equivalence Relation

Congruence modulo $n$ satisfies the three defining properties of an equivalence relation.

### Reflexivity

For every integer $a$,

$$
a\equiv a\pmod n,
$$

because

$$
a-a=0
$$

and

$$
n\mid0.
$$

### Symmetry

If

$$
a\equiv b\pmod n,
$$

then

$$
b\equiv a\pmod n.
$$

Indeed, if

$$
n\mid(a-b),
$$

then

$$
n\mid-(a-b)=b-a.
$$

### Transitivity

If

$$
a\equiv b\pmod n
$$

and

$$
b\equiv c\pmod n,
$$

then

$$
a\equiv c\pmod n.
$$

Since

$$
n\mid(a-b)
$$

and

$$
n\mid(b-c),
$$

we have

$$
n\mid[(a-b)+(b-c)]=a-c.
$$

Thus congruence partitions the integers into equivalence classes.

## Residue Classes

Modulo $n$, every integer belongs to exactly one of the residue classes

$$
0,1,2,\ldots,n-1.
$$

For example, modulo $5$, every integer is congruent to exactly one of

$$
0,1,2,3,4.
$$

The class of integers congruent to $2$ modulo $5$ is

$$
\{\ldots,-8,-3,2,7,12,17,\ldots\}.
$$

These integers differ from one another by multiples of $5$.

Residue classes form the foundation of modular arithmetic.

## Compatibility with Arithmetic

Congruence behaves well under addition, subtraction, and multiplication.

If

$$
a\equiv b\pmod n
$$

and

$$
c\equiv d\pmod n,
$$

then

$$
a+c\equiv b+d\pmod n,
$$

$$
a-c\equiv b-d\pmod n,
$$

and

$$
ac\equiv bd\pmod n.
$$

For example,

$$
17\equiv5\pmod{12}
$$

and

$$
8\equiv-4\pmod{12}.
$$

Therefore

$$
17+8\equiv5+(-4)\equiv1\pmod{12}.
$$

Indeed,

$$
25\equiv1\pmod{12}.
$$

Similarly,

$$
17\cdot8\equiv5\cdot(-4)\equiv-20\equiv4\pmod{12}.
$$

Since

$$
136\equiv4\pmod{12},
$$

the rule is confirmed.

## Cancellation

Congruences may sometimes be canceled.

If

$$
ac\equiv bc\pmod n
$$

and

$$
\gcd(c,n)=1,
$$

then

$$
a\equiv b\pmod n.
$$

However, cancellation is not always valid without the coprimality condition.

For example,

$$
2\cdot1\equiv2\cdot4\pmod6,
$$

since

$$
2\equiv8\pmod6.
$$

But

$$
1\not\equiv4\pmod6.
$$

The failure occurs because

$$
\gcd(2,6)\ne1.
$$

Thus modular arithmetic differs subtly from ordinary arithmetic.

## Congruence and Divisibility Tests

Congruences explain many elementary divisibility tests.

For example,

$$
10\equiv1\pmod9.
$$

Therefore

$$
10^k\equiv1^k\equiv1\pmod9.
$$

If

$$
n=a_0+a_1\cdot10+a_2\cdot10^2+\cdots+a_r\cdot10^r,
$$

then modulo $9$,

$$
n\equiv a_0+a_1+\cdots+a_r.
$$

Thus an integer is divisible by $9$ exactly when the sum of its decimal digits is divisible by $9$.

Similar arguments explain divisibility tests for $3$, $11$, and other integers.

## Role in Number Theory

Congruence relations transform divisibility into arithmetic on residue classes. They allow integers to be studied modulo a fixed modulus, reducing infinitely many integers to finitely many cases.

This idea is central throughout number theory. Congruences appear in primality testing, Diophantine equations, cryptography, quadratic residues, algebraic number theory, and modular forms.

The notation

$$
a\equiv b\pmod n
$$

is therefore one of the most important languages of arithmetic.