# Congruence Modulo

You may see an expression like:

**A ≡ B (mod C)**

This says that A is **congruent** to B modulo C.

We will discuss the meaning of **congruence modulo** by performing a thought experiment with the **regular modulo operator**.

Let’s imagine we were calculating mod 5 for all of the integers:

Suppose we labelled 5 **slices** 0,1,2,3,4. Then, for each of the integers, we put it into a **slice** that matched the value of the integer mod 5.

Think of these slices as buckets, which hold a set of numbers. For example, **26** would go in the slice labelled **1**, because **26** mod 5 = **1**.

Above is a figure that shows some integers that we would find in each of the slices.

It would be useful to have a way of expressing that numbers belonged in the **same slice**

(Notice 26 is in the same slice as 1, 6, 11, 16, 21 in above example).

A common way of expressing that two values are in the same slice, is to say they are in the same **equivalence class**.

The way we express this mathematically for mod C is: **A ≡ B (mod C)**

The above expression is pronounced A is **congruent to** B modulo C.

Examining the expression closer:

≡ is the symbol for congruence, which means the values

**A**and**B**are in the same**equivalence class**.**(mod C)**tells us what**operation**we applied to**A**and**B**.when we have both of these, we call “≡”

**congruence modulo C.**

### e.g. 26 ≡ 11 (mod 5)

(26 mod 5 = 1 so it is in the equivalence class for 1,

11 mod 5 = 1 so it is in the equivalence class for 1, as well)

Note, that this is different from A mod C. 26 ≠ 11 mod 5

# Insights into Congruence Modulo

We can gain some further insight behind what congruence modulo means by performing the same thought experiment using a positive integer **C**.

First, we would label **C** slices **0,1,2,...,C-2,C-1**.

Then, for each of the integers, we would put it into a slice that matched the value of the integer **mod C**.

Below is a figure that shows some representative values that we would find in each of the slices.

If we looked at the bucket labelled **0** we would find:

... -3C, -2C, -C, 0, C, 2C, 3C, ....

If we looked at the bucket labelled **1** we would find:

... 1-3C, 1-2C, 1-C, 1, 1+C, 1+2C, 1+3C, ....

If we looked at the bucket labelled **2** we would find:

... 2-3C, 2-2C, 2-C, 2, 2+C, 2+2C, 2+3C, ....

…....

If we looked at the bucket for **C-1** we would find:

... -1-2C, -1-C, -1, C-1, -1+2C,-1+3C, -1+4C, ....

**From this experiment we can make a key observation:**

The values in each of the slices are equal to the the label on the slice plus or minus some **multiple of C**.

This means the difference between **any two values** in a slice is **some multiple of C**.

This observation can help us understand equivalent statements and **equivalence classes** next.