§2.1 Congruence and Congruence Classes

Example 2.1.1: Basic Modulo Calculations

\( 17 ≡ 5 \pmod{6} \) because 6 divides \( 17 - 5 = 12 \). Similarly, \( 4 ≡ 25 \pmod{7} \) because 7 divides \( 4 - 25 = -21 \), and \( 6 ≡ -4 \pmod{5} \) because 5 divides \( 6 - (-4) = 10 \).

Properties of Congruence

In the notation "a ≡ b (mod n)", the symbols "≡" and "(mod n)" are really parts of a single symbol; "a ≡ b" by itself is meaningless. Some texts write "a =_n b" instead of "a ≡ b (mod n)". Although this single-symbol notation is advantageous, we shall stick with the traditional "(mod n)" notation here.

The symbol used to denote congruence looks very much like an equal sign. 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.

Theorem 2.1: Congruence Properties Theorem

Let n be a positive integer. For all a, b, c ∈ ℤ:

1. \(a ≡ a \pmod{n}\);
2. if \(a ≡ b \pmod{n}\), then \(b ≡ a \pmod{n}\);
3. if \(a ≡ b \pmod{n}\) and \(b ≡ c \pmod{n}\), then \(a ≡ c \pmod{n}\).

Proof of Theorem 2.1

(1) To prove that \(a ≡ a \pmod{n}\), we must show that \(n \mid (a - a)\). But \(a - a = 0\) and \(n \mid 0\) (see Example 2 on page 9). Hence, \(n \mid (a - a)\) and \(a ≡ a \pmod{n}\).

(2) \(a ≡ b \pmod{n}\) means that \(a - b = nk\) for some integer \(k\). Therefore, \(b - a = -(a - b) = -nk = n(-k)\). The first and last parts of this equation say that \(n \mid (b - a)\). Hence, \(b ≡ a \pmod{n}\).

(3) If \(a ≡ b \pmod{n}\) and \(b ≡ c \pmod{n}\), then by the definition of congruence, there are integers \(k\) and \(t\) such that \(a - b = nk\) and \(b - c = nt\). Therefore:

\((a - b) + (b - c) = nk + nt\),
\(a - c = n(k + t).\)

Thus, \(n \mid (a - c)\) and, hence, \(a ≡ c \pmod{n}\). ■

Several essential arithmetic and algebraic manipulations depend on this key fact:

If \(a = b\) and \(c = d\), then \(a + c = b + d\) and \(ac = bd\).

We now show that the same thing is true for congruence.

Theorem 2.2: Addition and Multiplication Congruence Theorem

If \(a \equiv b \pmod{n}\) and \(c \equiv d \pmod{n}\), then:

1. \(a + c \equiv b + d \pmod{n}\);
2. \(ac \equiv bd \pmod{n}\).

Proof of Theorem 2.2

(1) To prove that \(a + c \equiv b + d \pmod{n}\), we must show that \(n\) divides \((a + c) - (b + d)\). Since \(a \equiv b \pmod{n}\) and \(c \equiv d \pmod{n}\), we know that \(n \mid (a - b)\) and \(n \mid (c - d)\). Hence, there are integers \(k\) and \(t\) such that:

\(a - b = nk \quad \text{and} \quad c - d = nt\).

We use these facts to show that \(n\) divides \((a + c) - (b + d)\):

The last equation shows that \(n\) divides \((a + c) - (b + d)\). Hence, \(a + c \equiv b + d \pmod{n}\).

(2) We must prove that \(n\) divides \(ac - bd\).

The last equation shows that \(n \mid (ac - bd)\). Therefore, \(ac \equiv bd \pmod{n}\). \(\blacksquare\)

Definition of Congruence Class

Congruence Class: Let \(a\) and \(n\) be integers with \(n > 0\). The congruence class of \(a\) modulo \(n\) (denoted \([a]\)) is the set of all integers that are congruent to \(a\) modulo \(n\). That is:

\([a] = \{ b \mid b \in \mathbb{Z} \text{ and } b ≡ a \pmod{n} \}\).

To say that \(b ≡ a \pmod{n}\) means that \(b - a = kn\) for some integer \(k\), or equivalently, that \(b = a + kn\). Thus:

\([a] = \{ b \mid b ≡ a \pmod{n} \} = \{ b \mid b = a + kn \text{ with } k \in \mathbb{Z} \} \\ = \{ a + kn \mid k \in \mathbb{Z} \}.\)

*Note: The first two lines of this proof use a standard algebraic technique: rewrite 0 as \(-X + X\) for a suitable expression \(X\).

Example 2.1.2: Congruence Class Modulo 5

In congruence modulo 5, we have:

\([9] = \{9 + 5k \mid k \in \mathbb{Z}\} = \{9, 9 \pm 5, 9 \pm 10, 9 \pm 15, \dots\} \\ = \{\dots, -11, -6, -1, 4, 9, 14, 19, 24, \dots\}.\)

Example 2.1.3: Different Congruence Classes in Various Moduli

The meaning of the symbol \([ \cdot ]\) depends on the context. For instance, in congruence modulo 3, we have:

\([2] = \{2 + 3k \mid k \in \mathbb{Z}\} = \{\dots, -7, -4, -1, 2, 5, 8, \dots\},\)

but in congruence modulo 5, the congruence class \([2]\) is the set:

\([2] = \{2 + 5k \mid k \in \mathbb{Z}\} = \{\dots, -13, -8, -3, 2, 7, 12, \dots\}.\)

This ambiguity will not cause any difficulty when only one modulus is under discussion. On the few occasions when several moduli are discussed simultaneously, we avoid confusion by denoting the congruence class of \(a\) modulo \(n\) as \([a]_n\).

Example 2.1.4: Equivalent Congruence Classes Modulo 3

In congruence modulo 3, the congruence class:

\([2] = \{\dots, -7, -4, -1, 2, 5, 8, \dots\}.\)

Notice, however, that \([-1]\) is the same class because:

\([-1] = \{-1 + 3k \mid k \in \mathbb{Z}\} = \{\dots, -7, -4, -1, 2, 5, \dots\}.\)

Furthermore, \(2 ≡ -1 \pmod{3}\). This is an example of the following theorem.

Theorem 2.3: Equivalence of Congruence and Congruence Classes

\(a \equiv c \pmod{n}\) if and only if \([a] = [c]\).

Since Theorem 2.3 is an "if and only if" statement, we must prove two different things:

1. If \(a \equiv c \pmod{n}\), then \([a] = [c]\).
2. If \([a] = [c]\), then \(a \equiv c \pmod{n}\).

Neither of these proofs will use the definition of congruence. Instead, the proofs will use only the fact that congruence is reflexive, symmetric, and transitive (Theorem 2.1).

Proof of Theorem 2.3

First, assume that \(a \equiv c \pmod{n}\). To prove that \([a] = [c]\), we first show that \([a] \subseteq [c]\). Let \(b \in [a]\). Then by definition \(b \equiv a \pmod{n}\). Since \(a \equiv c \pmod{n}\), we have \(b \equiv c \pmod{n}\) by transitivity. Therefore, \(b \in [c]\) and \([a] \subseteq [c]\). Reversing the roles of \(a\) and \(c\) in this argument, and using the fact that \(c \equiv a\) by symmetry, shows that \([c] \subseteq [a]\). Therefore, \([a] = [c]\).

Conversely, assume that \([a] = [c]\). Since \(a \equiv a \pmod{n}\) by reflexivity, we have \(a \in [a]\) and hence \(a \in [c]\). By the definition of \([c]\), we see that \(a \equiv c \pmod{n}\). \(\blacksquare\)

Corollary 2.4: Disjointness or Identity of Congruence Classes

Two congruence classes modulo \(n\) are either disjoint or identical.

Proof of Corollary 2.4

If \([a]\) and \([c]\) are disjoint, there is nothing to prove. Suppose that \([a] \cap [c]\) is nonempty. Then there is an integer \(b\) with \(b \in [a]\) and \(b \in [c]\). By the definition of congruence class, \(b \equiv a \pmod{n}\) and \(b \equiv c \pmod{n}\). Therefore, by symmetry and transitivity, \(a \equiv c \pmod{n}\). Hence, \([a] = [c]\) by Theorem 2.3. \(\blacksquare\)

Corollary 2.5: Distinct Congruence Classes Modulo \(n\)

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], [2], \dots, [n-1]\).

Proof of Corollary 2.5

(1) Let \(a \in \mathbb{Z}\). By the Division Algorithm, \(a = nq + r\), with \(0 \leq r < n\). Thus, \(a - r=nq\), so that \(a \equiv r \pmod{n}\). By Theorem 2.3, \([a]=[r]\).

(2) If \([a]\) is any congruence class, then (1) shows that \([a] = [r]\) with \(0 \leq r < n\). Hence, \([a]\) must be one of \([0], [1], [2], \dots, [n-1]\).

To complete the proof, we must show that these \(n\) classes are all distinct. Suppose that \(s\) and \(t\) are distinct integers in the list \(0, 1, 2, \dots, n-1\). Since \(s < t < n\), we have \(t - s\) as a positive integer less than \(n\). Hence, \(n\) does not divide \(t - s\), which means \(t \not\equiv s \pmod{n}\). Therefore, by Theorem 2.3, the classes \([0], [1], [2], \dots, [n-1]\) are all distinct. \(\blacksquare\)

Definition of \(\mathbb{Z}_n\) ("Z mod n")

The set of all congruence classes modulo \(n\) is denoted \(\mathbb{Z}_n\) (which is read "Z mod n").

There are several points to be careful about here. The elements of \(\mathbb{Z}_n\) are classes, not single integers. So the statement \([5] \in \mathbb{Z}_n\) is true, but the statement \(5 \in \mathbb{Z}_n\) is not. Furthermore, every element of \(\mathbb{Z}_n\) can be denoted in many different ways. For example, we know that:

\(2 \equiv 5 \pmod{3}, \quad 2 \equiv -1 \pmod{3}, \quad 2 \equiv 14 \pmod{3}.\)

Therefore, by Theorem 2.3, \([2] = [5] = [-1] = [14]\) in \(\mathbb{Z}_3\). Even though each element of \(\mathbb{Z}_n\) (that is, each congruence class) has infinitely many different labels, there are only finitely many distinct classes by Corollary 2.5, which says in effect that:

The set \(\mathbb{Z}_n\) has exactly \(n\) elements.

For example, the set \(\mathbb{Z}_3\) consists of the three elements \([0], [1], [2]\).