[Introduction to Number Theory Series Part 11] Why Is Congruence the Language of Remainders?

In the earlier part of the series, we viewed integers through divisibility, gcds, and prime factorization. Now we shift perspective. Instead of asking how far apart two integers are, we ask whether they leave the same remainder.

What this post covers

• The meaning of a \equiv b \pmod n
• Why equal remainders and divisibility of the difference are the same idea
• A few basic examples
• Why congruence opens the door to modular arithmetic

Key terms

• congruence: the relation of having the same remainder modulo n
• remainder: the value left after division
• modular arithmetic: computation based on remainders
• divisibility: the relation of exact division

The definition of congruence

Let a, b, and n be integers with n>0. We write

$$a \equiv b \pmod n$$

when a and b have the same remainder upon division by n.

This is equivalent to saying

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

The condition n>0 matters because congruence is always defined with respect to a positive modulus. It gives us a standard remainder system to work with.

Why are these two views equivalent?

Take 17 and 5 modulo 4.

• 17 = 4\times 4 + 1
• 5 = 4\times 1 + 1

They have the same remainder, so

$$17 \equiv 5 \pmod 4.$$

Now look at the difference:

$$17-5=12,$$

and 12 is divisible by 4. So congruence links two perspectives:

• a computational view: same remainder
• a structural view: difference divisible by the modulus

More examples

14 \equiv 2 \pmod 6

Both leave remainder 2 modulo 6, and

$$14-2=12$$

is divisible by 6.

20 \equiv 6 \pmod 7

Both leave remainder 6 modulo 7.

11 \equiv 3 \pmod 4

Both leave remainder 3 modulo 4.

Why is congruence useful?

Congruence lets us replace large numbers with smaller representatives. Since

$$101 \equiv 1 \pmod 5,$$

we can often compute with 1 instead of 101 in the modular world. That is the basic power of congruence, and the next post turns that idea into actual arithmetic rules.

Common mistakes

1. Treating congruence as ordinary equality

a \equiv b \pmod n does not mean a=b. It means they belong to the same remainder class modulo n.

2. Omitting the modulus

Congruence is always with respect to some modulus.

3. Remembering only the remainder version

The divisibility version n | (a-b) is often the better form in proofs.

Wrap-up

Congruence says that two integers have the same remainder modulo n, or equivalently that their difference is divisible by n.

Next we use this relation to perform actual computations in modular arithmetic.