The congruence (the modulo)

Where does it come from?

Congruence was formally studied for the first time at the end of the 18th century and the very beginning of the 19th century by Carl Friedrich Gauss, the “master” of mathematicians.

He gave his name to the bell curve known as the “Gaussian curve.”

Note: This post was translated from french with the help of AI. The original post was written with the knowledge of a younger me.

Before that, people used congruence without being aware of its properties, just as we know how to add 2 carrots and 3 carrots without realizing it’s a sum in arithmetic.

That’s all very nice, but… what is it, exactly?

The principle

Congruence is a mathematical structure. That is, a set of rules, that allows us to relate integers to one another within a finite set.

That is, if we consider a congruence of modulus (or modulo) n (we’ll see later what a modulus is), we have the following properties:

$$ a \equiv a \pmod{n} $$ $$ \text{if } a \equiv b \pmod{n} \quad \text{then } b \equiv a \pmod{n} $$ $$ \text{if } a \equiv b \pmod{n} \quad \text{and } b \equiv c \pmod{n} \quad \text{then } a \equiv c \pmod{n} $$ $$ \text{if } a \equiv b \pmod{n} \quad \text{and } c \equiv d \pmod{n} \quad \text{then } a+c \equiv b+d \pmod{n} \quad \text{and } a \times c \equiv b \times c \pmod{n} $$

And here you’re probably thinking: “I don’t get it. Why are there three bars in that equal sign? What does mod mean? So many questions!”

Don’t worry. We’ll go through examples and clearer illustrations.

Looping around

Another way to think about congruence and modulo is as a loop or cycle.

A small example: minutes

Imagine you’re looking at a clock and paying attention only to the minute hand.

You want to add 45 minutes and 30 minutes, but you don’t care about the hour (just the minute hand). What do you get?

15 minutes, right?

Congratulations—you’ve just done a modulo 60 congruence calculation.

And you can add numbers much larger than 60 (or any other modulus). You simply subtract 60 from the result as many times as you can. The result must lie within the set (here, between 0 and 59).

How much is 59 + 258 minutes modulo 60?

Answer at the end of this blog post.

A second small example: hours

Now, with hours. You look only at the hour hand (ignore the minutes). You add 5 hours to 8 hours. What do you get? Careful, it’s a clock.

1 o’clock, right? (since a clock only shows 12 hours)

You’ve just done a modulo 12 congruence calculation.

So, why an equal sign with three lines? Because in this second example, the result is not equal to 1 in the strict sense. We removed some extra hours. So we write it with this sign called “congruent to.”

You can see that we can add huge numbers while keeping the result within a limited set of numbers (a finite set). The size of the congruence limits the possible results. Here, for example, the set contains 12 numbers, the 12 hours of a clock.

Of course, since it’s a cycle, it also works with subtracting hours and with negative integers. You simply add the modulus afterward to bring the result back into the set (here, between 0 and 11).

So, how much is 2 – 18 hours modulo 12?

Answer at the end of this blog post.

Another example: fingers

If you consider the fingers of one hand, you have a congruence of 5 (usually), and with two hands, a congruence of 10.

Not convinced?

Take just one hand and count with your fingers: 3 + 4. How many fingers remain?

2, I think.

Now, take two hands and count 8 + 9. How many fingers remain?

7, right?

I’m deliberately using the term “remainder.” You’ll see why.

And the remainder?

You can also think of congruence as the remainder of a division (Euclidean division, for those who know the term).

The denominator of the division (the number below) is the modulus, and when you’ve finished dividing, what’s left is the remainder.

Note: it’s important to remember that this works with integers, so no decimals. You stop your division before the remainder becomes a decimal.

So, if we divide 3 by 2, what remainder do we get?

1, of course.

And if we divide 5 by 2, what remainder?

Also 1. Not bad.

So that means 1 ≡ 3 mod(2) and 1 ≡ 5 mod(2), right?

And therefore:

$$ 1 \equiv 3 \pmod{2} \equiv 5 \pmod{2} $$

Now, are the remainders of 33 ÷ 26 and 85 ÷ 26 congruent?

Answers

How much is 59 + 258 minutes modulo 60?

$$ 59+258 = 317 \equiv 317-60 \times 5 \pmod{60} $$

(we have 5 times 60 that fits in 317)

$$ \equiv 317-300 \pmod{60} \equiv 17 \pmod{60} $$

So:

$$ 59+258 \equiv 17 \pmod{60} $$

How much is 2 – 18 hours modulo 12?

$$ 2-18 = -16 \equiv -16+12 \pmod{12} \equiv -4 \pmod{12} $$

(it’s still negative, so not between 0 and 11)

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

So: $$ 2-18 \equiv 8 \pmod{12} $$

Are the remainders of 33 ÷ 26 and 85 ÷ 26 congruent?

$$ 33/26 = (26+7)/26 $$

so the remainder is 7.

$$ 85/26 = (26+59)/26 $$

59 is greater than 26, so we continue:

$$ = (26+26+33)/26 $$

well look, 33, just like in the first division—so we continue:

$$ = (26+26+26+7)/26 $$

so the remainder is 7.

Therefore, yes, the remainders of 33 ÷ 26 and 85 ÷ 26 are congruent.