Congruence Modulo

You may see an expression like:
AB(mod C) A \equiv B (\text{mod } C)
This says that A A is congruent to B B modulo C 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 26 \text{ mod } 5 = \bf{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: AB (mod C) A \equiv B \ (\text{mod } C)
The above expression is pronounced A A is congruent to B B modulo C C .
Examining the expression closer:
  1. \equiv is the symbol for congruence, which means the values A A and B B are in the same equivalence class.
  2. (mod C) (\text{mod } C) tells us what operation we applied to A A and B B .
  3. when we have both of these, we call “ \equiv congruence modulo C C .
e.g. 2611 (mod 5) 26 \equiv 11\ (\text{mod }5)
26 mod 5=1 26 \text{ mod } 5 = 1 so it is in the equivalence class for 1,
11 mod 5=1 11 \text{ mod } 5 = 1 so it is in the equivalence class for 1, as well.
Note, that this is different from A mod C A \text{ mod } C : 2611 mod 5 26 \neq 11 \text { 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 C .
First, we would label C C slices 0,1,2,,C2,C1 0, 1, 2, \ldots, 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 \text{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, \ldots, -3C, -2C, -C, 0, C, 2C, 3C, \ldots
If we looked at the bucket labelled 1 we would find:
,13C,12C,1C,1,1+C,1+2C,1+3C, \ldots, 1-3C, 1-2C, 1-C, 1, 1+C, 1+2C, 1+3C, \ldots
If we looked at the bucket labelled 2 we would find:
,23C,22C,2C,2,2+C,2+2C,2+3C, \ldots, 2-3C, 2-2C, 2-C, 2, 2+C, 2+2C, 2+3C, \ldots
If we looked at the bucket for C1 C - 1 we would find:
,2C1,C1,1,C1,2C1,3C1,4C1 \ldots, -2C-1, -C-1, -1, C-1, 2C - 1, 3C-1, 4C - 1 \ldots
From this experiment we can make a key observation:
The values in each of the slices are equal to the label on the slice plus or minus some multiple of C \bf{C} .
This means the difference between any two values in a slice is some multiple of C \bf{C} .
This observation can help us understand equivalent statements and equivalence classes next.
Loading