Congruence Modulo

You may see an expression like:
AB(mod C) A \equiv B (\text{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:
moed
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 .
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 is congruent to B modulo C.
Examining the expression closer:
  1. \equiv is the symbol for congruence, which means the values A and B are in the same equivalence class.
  2. left parenthesis, m, o, d, space, C, right parenthesis tells us what operation we applied to A and B.
  3. when we have both of these, we call “ \equiv congruence modulo C.
e.g. 2611 (mod 5) 26 \equiv 11\ (\text{mod }5)
26, space, m, o, d, space, 5, equals, 1 so it is in the equivalence class for 1,
11, space, m, o, d, space, 5, equals, 1 so it is in the equivalence class for 1, as well.
Note, that this is different from A, space, m, o, d, space, C: 26, does not equal, 11, space, m, o, d, space, 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,,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 m, o, d, space, 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 C, minus, 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 .
This means the difference between any two values in a slice is some multiple of .
This observation can help us understand equivalent statements and equivalence classes next.