Skip to content

Congruence Relations

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

number-theory book chatgpt

Motivation

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

For example, the integers

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

leave the same remainder when divided by 1212:

17=12⋅1+5,5=12⋅0+5. 17=12\cdot1+5, \qquad 5=12\cdot0+5.

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

This observation leads to the notion of congruence.

Definition of Congruence

Let a,b∈Za,b\in\mathbb{Z}, and let n∈Nn\in\mathbb{N}.

We say that aa is congruent to bb modulo nn if

n∣(a−b). n\mid(a-b).

This is written

a≡b(modn). a\equiv b\pmod n.

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

For example,

17≡5(mod12), 17\equiv5\pmod{12},

because

17−5=12 17-5=12

and

12∣12. 12\mid12.

Similarly,

29≡1(mod7), 29\equiv1\pmod7,

since

29−1=28 29-1=28

and

7∣28. 7\mid28.

Congruence and Remainders

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

For example,

23≡8(mod5) 23\equiv8\pmod5

because both integers leave remainder 33 when divided by 55:

23=5⋅4+3,8=5⋅1+3. 23=5\cdot4+3, \qquad 8=5\cdot1+3.

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

Examples

Modulo 22

Every integer is congruent either to 00 or to 11 modulo 22.

Even integers satisfy

a≡0(mod2), a\equiv0\pmod2,

while odd integers satisfy

a≡1(mod2). a\equiv1\pmod2.

Thus parity is congruence modulo 22.

Modulo 1010

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

For example,

137≡7(mod10). 137\equiv7\pmod{10}.

Similarly,

254≡4(mod10). 254\equiv4\pmod{10}.

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

Congruence as an Equivalence Relation

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

Reflexivity

For every integer aa,

a≡a(modn), a\equiv a\pmod n,

because

a−a=0 a-a=0

and

n∣0. n\mid0.

Symmetry

If

a≡b(modn), a\equiv b\pmod n,

then

b≡a(modn). b\equiv a\pmod n.

Indeed, if

n∣(a−b), n\mid(a-b),

then

n∣−(a−b)=b−a. n\mid-(a-b)=b-a.

Transitivity

If

a≡b(modn) a\equiv b\pmod n

and

b≡c(modn), b\equiv c\pmod n,

then

a≡c(modn). a\equiv c\pmod n.

Since

n∣(a−b) n\mid(a-b)

and

n∣(b−c), n\mid(b-c),

we have

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

Thus congruence partitions the integers into equivalence classes.

Residue Classes

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

0,1,2,…,n−1. 0,1,2,\ldots,n-1.

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

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

The class of integers congruent to 22 modulo 55 is

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

These integers differ from one another by multiples of 55.

Residue classes form the foundation of modular arithmetic.

Compatibility with Arithmetic

Congruence behaves well under addition, subtraction, and multiplication.

If

a≡b(modn) a\equiv b\pmod n

and

c≡d(modn), c\equiv d\pmod n,

then

a+c≡b+d(modn), a+c\equiv b+d\pmod n, a−c≡b−d(modn), a-c\equiv b-d\pmod n,

and

ac≡bd(modn). ac\equiv bd\pmod n.

For example,

17≡5(mod12) 17\equiv5\pmod{12}

and

8≡−4(mod12). 8\equiv-4\pmod{12}.

Therefore

17+8≡5+(−4)≡1(mod12). 17+8\equiv5+(-4)\equiv1\pmod{12}.

Indeed,

25≡1(mod12). 25\equiv1\pmod{12}.

Similarly,

17⋅8≡5⋅(−4)≡−20≡4(mod12). 17\cdot8\equiv5\cdot(-4)\equiv-20\equiv4\pmod{12}.

Since

136≡4(mod12), 136\equiv4\pmod{12},

the rule is confirmed.

Cancellation

Congruences may sometimes be canceled.

If

ac≡bc(modn) ac\equiv bc\pmod n

and

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

then

a≡b(modn). a\equiv b\pmod n.

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

For example,

2⋅1≡2⋅4(mod6), 2\cdot1\equiv2\cdot4\pmod6,

since

2≡8(mod6). 2\equiv8\pmod6.

But

1≢4(mod6). 1\not\equiv4\pmod6.

The failure occurs because

gcd⁡(2,6)≠1. \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≡1(mod9). 10\equiv1\pmod9.

Therefore

10k≡1k≡1(mod9). 10^k\equiv1^k\equiv1\pmod9.

If

n=a0+a1⋅10+a2⋅102+⋯+ar⋅10r, n=a_0+a_1\cdot10+a_2\cdot10^2+\cdots+a_r\cdot10^r,

then modulo 99,

n≡a0+a1+⋯+ar. n\equiv a_0+a_1+\cdots+a_r.

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

Similar arguments explain divisibility tests for 33, 1111, 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≡b(modn) a\equiv b\pmod n

is therefore one of the most important languages of arithmetic.