The Definition of Congruence in the Modular Systems

September 1, 2012 GB College Mathematics, Number Theory

This is the fourth part of the Introduction to the Modular Number Systems Series. In the previous parts, we have learned intuitively the modular systems using a 12-hour analog clock, performed operations with its numbers and introduce the symbol for congruence, and discussed the different number bases. In this post, we formally define congruence.

image via Wikipedia

Recall that the statement $17 \equiv 5 (\mod 12)$ means that 17 gives a remainder of 5 when divided by 12, or that 17 and 5 give the same remainder when divided by 12. We have also learned that 17, 29, and 41 are congruent since all of them give the same remainder (that is 5) when divided by 12. Notice also that since all of them are congruent,

17 = 12(1) + 5

29 = 12(2) + 5

41 = 12(3) + 5

This means that if we subtract 5 from these numbers, they will all be divisible by 12. Equivalently,

$17 \equiv 5 (\mod 12)$

if and only if 17 – 5 is divisible by 12. This statement is also true with 29 and 41. That is, 29 – 5 = 24 is divisible by 12 and that 41 – 5 = 36 is divisible by 12. All of the results after the subtraction are multiples of 12, so for any integer $k$

$(12k + 5) \equiv 5 (\mod 12)$

if and only if $(12k + 5) - 5$ is divisible by 12.

In general, we say that $a$ is congruent to $b$ modulo $m$ and write

$a \equiv b (\mod m)$

if an only if $a - b$ is divisible by $m$ . We should remember that in this definition, $a$ and $b$ are integers and $m$ is a positive integer. Now, $a - b$ is divisible by $m$ , we can find an integer $k$ (the quotient), such that