Modular Arithmetic - Congruence Relation

Congruence Relation

Modular arithmetic can be handled mathematically by introducing a congruence relation on the integers that is compatible with the operations of the ring of integers: addition, subtraction, and multiplication. For a positive integer n, two integers a and b are said to be congruent modulo n, written:

if their difference a − b is an integer multiple of n. The number n is called the modulus of the congruence.

For example,

because 38 − 14 = 24, which is a multiple of 12.

The same rule holds for negative values:

When and are either both positive or both negative, then can also be thought of as asserting that both and have the same remainder. For instance:

because both and have the same remainder, . It is also the case that is an integer multiple of, which agrees with the prior definition of the congruence relation.

A remark on the notation: Because it is common to consider several congruence relations for different moduli at the same time, the modulus is incorporated in the notation. In spite of the ternary notation, the congruence relation for a given modulus is binary. This would have been clearer if the notation a ≡_n b had been used, instead of the common traditional notation.

The properties that make this relation a congruence relation (respecting addition, subtraction, and multiplication) are the following.

If

and

then:

It should be noted that the above two properties would still hold if the theory were expanded to include all real numbers, that is if were not necessarily all integers. The next property, however, would fail if these variables were not all integers: