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.
Recall that the statement 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,
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
if and only if is divisible by 12.
In general, we say that is congruent to modulo and write
if an only if is divisible by . We should remember that in this definition, and are integers and is a positive integer. Now, is divisible by , we can find an integer (the quotient), such that
which means that
Therefore, another definition which is equivalent to the definition above is
if and only if where is an integer.
With this definition, it is easy to integrate negative integers to modular systems. For example,
since -7 – 5 is divisible by 12. We can also say that
since is divisible by 3. It is also easy to see that
if , then .
The proof of this observation is left as an exercise.