Congruence modulo n

We focus in this paragraph on an important relation in ℤ, the congruence relation modulo a positive integer n.

Definition 4.1.1. Let n be a given natural number. The Congruence modulo relation is defined thus:

To say that n divides a − b is to say that a − b = nk for some integer k.

For example, we can write 38 ≡ 14   (mod 12), because 38 − 14 = 24, which is a multiple of 12.

It easy to verify that this is an equivalence relation. So we may consider the equivalence classes, called congruence classes modulo n or residue classes modulo n, defined by this relation in a way to “lump together” into a single set integers which are congruent modulo r and then treat that set as a single mathematical object.

Definition 4.1.2. Given an integer a, we shall denote by [a]_n, or, if no confusion may possibly arise, by [a], or by ā, the congruence class of a modulo n, is

i.e.: "congruent integers to a modulo n" are those that may written in the form a + nh for a particular h ∈ ℤ. Indeed, if b ≡_n a thus b − a is a multiple of n, so b − a = nh for a particular h ∈ ℤ, i.e.: b = a + nh. This is the reason why equivalence classes modulo n are also called residue classes modulo n.

Theorem 4.1.3. a ≡ c (mod n) if and only if [a] = [c].

Proof. We must prove two things to meet the condition "if and only if"

1. If a ≡ c (mod n), then [a] = [c].

2. If [a] = [c], the [a] = [c].

We won't use the definition of congruence. Instead we use the fact that congruence is an equivalence relation hence reflexive, symmetric and transitive.

Assume first that a ≡ c (mod n). To prove that [a] = [c], we first show that [a] ⊆ [c]. To do this, let b ∈ [a]. Then by definition b ≡ a (mod n). Since a ≡ c (mod n), we have b ≡ c (mod n) by transitivity. Therefore, b ∈ [c] and [a] ⊆ [c]. Reversing the roles of a and c in this argument and using symmetry that is c ≡ a (mod n) is shown that [c] ⊆ [a]. Therefore, [a] = [c].

Conversely, assume that [a] = [c]. Since a ≡ a (mod n) by reflexivity, we have a ∈ [a] and, hence, a ∈ [c]. By definition of [c], we see that a ≡ c (mod n).□

Proposition 4.1.4. a ≡ b (mod n) if and only if a and b leave the same remainder when divided by n. Conversely if a and b leave the same remainder when divided by n, then a ≡ b mod n.

Proof. By definition of congruence a = b + hn for some integer h. By the division algorithm, b = nq + r where 0 ≤ r < n. Then a = b + hn = (nq + r) + hn = n(q + h) + r; therefore, by the division algorithm, a leaves the same remainder r when divided by n.
Conversely, suppose both a and b leave the same remainder r when divided by n. Then, again by the division algorithm, a = nq + r and b = nq' + r, where 0 ≤ r < n. Then a − b = (nq + r) − (nq' + r) = n(q − q'), so a ≡ b (mod n). □

For example 6 and 8 are congruent mod 2 because they have the same remainder r = 2 on division by 2.

If A and B are two sets, there are usually three possibilities: Either A and B are disjoint, or A = B, or A ∩ B is nonempty but A ≠ B. With congruence classes, however, there are only two possibilities:

Proposition 4.1.5. Two congruence classes modulo n are either disjoint or identical.

Proof. If [a] and [c] are disjoint, we are done. Suppose they are not, so [a] ∩ [c] is nonempty. Then there is an integer b with b ∈ [a] and b ∈ [c]. By definition of congruence class, b ≡ a (mod n) and b ≡ c (mod n). Therefore, by symmetry and transitivity, a ≡ c (mod n). Hence [a] = [c], by theorem 4.2.1, so if they are not disjoint they are identical.□

Corollary 4.1.6. Let n > 1 be an integer and consider congruence modulo n

1. If a is any integer and r is the remainder when a is divided by n, then [a] = [r].

2. There are exactly n distinct congruence classes, namely [0], [1], [n − 1].

Proof. Let a ∈ℤ by the division algorithm dividing by n, a = nq + r, with 0 ≤ r < n. Thus a − r = qn so that a ≡ r (mod n). By theorem 4.2.1 [a] = [r]. The possible remainders are 0, 1, 2, ..., n − 1, that is there will be exactly n equivalence classes.

To complete the proof, we must show that these n classes are all distinct. To do this, we first show that no two of 0, 1, 2, ... , n − 1 are congruent modulo n. Suppose that s and t are distinct integers in the list 0, 1 , 2, ..., n − 1. Then one is larger than the other, say r, so that 0 ≤ s < t < n. Consequently, t − s is a positive integer that is less than n. Hence, n does not divide t − s, which means that t ≠ s. Thus, no two of 0, 1, 2, ... , n − 1 are congruent modulo n. Therefore, by Theorem 4.2.1, the classes [0], [1], [2], ... , [n − 1] are all distinct.□

Corollary 4.1.7. Every integer is congruent (mod n) to exactly one of the numbers in the list:

this number is indicated as

Proof. As we may always divide an integer a by n (see proposition 2.3), if we denote by r the remainder of the division every integer a is congruent modulo n to an integer r such that 0 ≤ r < n, in fact a = r + nh ⇒ a − r = nh.□

We indicate the set of all congruence classes of integers modulo n with ℤ_n or ℤ/nℤ

Be careful to note that we are considering here a set of sets: Each element of the finite set ℤ_n is in fact an infinite set of the form [k].

These n residue classes then partition the integers, meaning that each integer belongs to exactly one of these classes, and if distinct classes intersect, they are in fact equal. Alternatively, this means that

and the sets in this union are disjoint from one another pairwise. In particular, we have that

If we consider ℤ₉, every element of [k] falls into one of the first nine groups, from [0]₉ to [8]₉ and no number falls into more than one group, because as we have seen

If n = 2, we only two possible remainder, 0 and 1 and consequently two classes, [0] e [1]: the first contains all integers {2k | k ∈ ℤ} the second all integers 2k + 1 | k ∈ ℤ }, i.e. the partition induced on ℤ is that of even and odd numbers.

For example the class [2]₉ is made by integers of the form 2 + 9h for h ∈ ℤ equal to 0, 1, 2, 3, etc. we have thus 2 = 2 + 9 · 0, 11 = 2 + 9 · 1, 20 = 2 + 9 · 2, 29 = 2 + 9 · 3, and so forth, for negative h we obtain −7 = 2 + 9 · (−1), −16 = 2 + 9 · (−2), −25 = 2 + 9 · (−3), and so on. We have thus:

[0]₉ = {..., 0, 9, 18, 27, 36, ...} = {x ∈ ℤ | x ≡ 0 (mod 9)}
[1]₉ = {..., 1, 10, 19, 28, 37, ...} = {x ∈ ℤ | x ≡ 1 (mod 9)}
[2]₉ = {..., 2, 11, 20, 29, 38, ...} = {x ∈ ℤ | x ≡ 2 (mod 9)}
[3]₉ = {..., 3, 12, 21, 30, 39, ...} = {x ∈ ℤ | x ≡ 3 (mod 9)}
[4]₉ = {..., 4, 13, 22, 31, 40, ...} = {x ∈ ℤ | x ≡ 4 (mod 9)}
[5]₉ = {..., 5, 14, 23, 32, 41, ...} = {x ∈ ℤ | x ≡ 5 (mod 9)}
[6]₉ = {..., 6, 15, 24, 33, 42, ...} = {x ∈ ℤ | x ≡ 6 (mod 9)}
[7]₉ = {..., 7, 16, 25, 34, 43, ...} = {x ∈ ℤ | x ≡ 7 (mod 9)}
[8]₉ = {..., 8, 17, 26, 35, 44, ...} = {x ∈ ℤ | x ≡ 8 (mod 9)}
..
[20]₉ = {..., 20, 29, 38, 46, 55, ... } = {x ∈ ℤ | x ≡ 20 (mod 9)
..

Each element of ℤ_n can be denoted in many different ways. For example, we know that

Therefore, by Theorem 4.2.1, [2] = [5] = [−1] = [14] in ℤ₃.

For every integer a ∈ ℤ there is a congruence class [a] ∈ ℤ_n. Even though each element of ℤ_n (that is, each congruence class) has infinitely many different labels, there are only finitely many distinct classes by Corollary 4.0.6, which says in effect that

The set ℤ₃ consists of the three elements [0], [1], [2]. The elements [3], [4], [5], ... are just repetitions of [0], [1], [2], ....

It is easily checked that the map

which assigns to each residue class [a] the least non-negative residue of a modulo n, is a bijection.

Another definition of equivalence class by virtue of Corollary 4.0.4 is the following

Properties of ≡

The symbol used to denote congruence looks very much like an equal sign. The symbol ≡ was introduced by Gauss in the Disquisitiones, by virtue of the analogy with the equality relation. This is no accident since the relation of congruence has many of the same properties as the relation of equality. For example, we know that equality is

Reflexive: a = a for every integer a;

Symmetric: if a = b, then b = a;

Transitive: if a = b and b = c, then a = c.

We now see that congruence modulo n is also reflexive, symmetric, and transitive that is: an equivalence relation.

Notice that an integer is congruent to every other integer modulo 1, that is to say congruence modulo 1 is a trivial equivalence relation; for this reason in what follows we shall in general assume n > 1.

Congruence gets along well with addition and multiplication.