The Definition of Congruence in the Modular Systems

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.

modular systems

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

\displaystyle\frac{a - b}{m} = k

which means that a - b = mk

Therefore, another definition which is equivalent to the definition above is

a \equiv b (\mod m) if and only if a - b = km where k is an integer.

With this definition, it is easy to integrate negative integers to modular systems. For example,

-7 \equiv 5 (\mod 12)

since -7 – 5 is divisible by 12. We can also say that

18 \equiv - 9 (\mod 3)

since 18 - (-9) is divisible by 3.  It is also easy to see that

if a \equiv b (\mod m), then  b \equiv a (\mod m).

The proof of this observation is left as an exercise.

Leave a Reply