Week 4 - Day 1: Congruence and Congruence Classes

§2.1 Congruence and Congruence Classes

Definition

Fix some \( n \in \mathbb{N} \) (called the modulus). For \( a, b \in \mathbb{Z} \), we say that \( a \) is congruent to \( b \) modulo \( n \) and write \( a \equiv b \pmod{n} \) provided that:

\[ n \mid (a - b). \]

(Their difference is a multiple of \( n \))

True/False Examples

\[ 11 \equiv 23 \pmod{12} \]

We calculate:

\[ 11 - 23 = -12 = 12(-1), \]

So, \( 12 \mid (11 - 23) \). True (military time example).

\[ 3(65) \equiv 1 \pmod{7} \]

We calculate:

\[ 365 - 1 = 364 = 52 \times 7, \]

So, \( 7 \mid (365 - 1) \). True (day of the week example).

Another Point of View

\[ a \equiv b \pmod{n} \iff n \mid (a - b) \]
\[ \iff a - b = nk \quad \text{for some } k \in \mathbb{Z} \]
\[ \iff a = b + nk \quad \text{for some } k \in \mathbb{Z}. \]

Two numbers are congruent modulo \( n \) if you can get from one to the other by adding or subtracting multiples of \( n \).

Important Special Case

Which integers are congruent to \( 0 \) modulo \( n \)?

\[ x \equiv 0 \pmod{n} \iff n \mid (x - 0) \]
\[ \iff x \text{ is a multiple of } n. \]

Intuition

Mod \( n \) arithmetic is like normal arithmetic, except as if \( n \) were treated like 0.

Example

\[ 3 + 11 \equiv 2 \pmod{12} \]

(Clock arithmetic)

Theorem (HW)

Congruence modulo \( n \) is an equivalence relation.

For example, it's transitive...

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

Theorem

Recall that \( a \) and \( b \) leave the same remainder modulo \( n \) if and only if:

\[ n \mid (a - b). \]

Theorem (Equivalent Condition for Congruence)

\[ a \equiv b \pmod{n} \iff a \text{ and } b \text{ leave the same remainder mod } n. \]

So, modular arithmetic glues together integers that leave the same remainder.

Corollary

Every integer \( a \) is congruent to its remainder mod \( n \).

Example

\[ 15 \equiv 1 \pmod{7}. \]

Proof

Let \( a \in \mathbb{Z} \). By the Division Algorithm (DA), \( a = nq + r \) for some \( q, r \in \mathbb{Z} \), where \( r \) is the remainder when \( a \) is divided by \( n \). Thus, \( a - r = nq \), hence \( n \mid (a - r) \), and therefore \( a \equiv r \pmod{n} \). \(\square\)

Question

Using modulus \( N = 3 \), what are the first 4 natural numbers that are congruent to 1?

\[ [1] = \{ \dots, -2, 1, 4, 7, 10, 13, \dots \}. \]

Congruence Classes

Recall: Given an equivalence relation, the set of elements that are equivalent to a given element \( a \) is called the equivalence class of \( a \), denoted \([a]\).

When the relation is congruence, we call them Congruence Classes.

In general:

\[ [a] = \{ b \in \mathbb{Z} : b \equiv a \pmod{n} \} \]
\[ = \{ b \in \mathbb{Z} : n \mid (b - a) \} \]
\[ = \{ b \in \mathbb{Z} : b = a + nk \text{ for some } k \in \mathbb{Z} \} \]
\[ = a + n\mathbb{Z}. \]

Example (Using Modulus \( n = 3 \))

\[ [-1] = -1 + 3\mathbb{Z} = \{ \dots, -4, -1, 2, 5, \dots \} \]
\[ [0] = 0 + 3\mathbb{Z} = \{ \dots, -3, 0, 3, 6, \dots \} \]
\[ [1] = 1 + 3\mathbb{Z} = \{ \dots, -2, 1, 4, 7, \dots \} \]
\[ [2] = 2 + 3\mathbb{Z} = \{ \dots, -1, 2, 5, 8, \dots \} \]
\[ [3] = 3 + 3\mathbb{Z} = \{ \dots, 0, 3, 6, 9, \dots \} \]
\[ [4] = 4 + 3\mathbb{Z} = \{ \dots, 1, 4, 7, 10, \dots \}. \]

Visualization of Equivalence Classes

The mapping \( \pi(x) = [x] \) represents the equivalence classes.

Definition

The number \( a \) is called a representation of the class \( [a] \).

Note

For \( n = 3 \), since \( [1] = [4] \), the same class can have different representations.

Recall

In general, \( a \equiv b \iff [a] = [b] \).

Theorem 2.3

Two integers are congruent if and only if they represent the same class:

\[ a \equiv b \ (\text{mod} \ n) \iff [a] = [b]. \]

Definition

The set \( \mathbb{Z}_n \) is the set of congruence classes of integers modulo \( n \). That is:

\[ \mathbb{Z}_n = \{ [a] : a \in \mathbb{Z} \}. \]

Note

A priori, \( \mathbb{Z}_n \) appears to be infinite, containing one class per integer. But it isn’t!

Example

Consider the case \( n = 3 \):

\[ \mathbb{Z}_3 = \{ \dots, [-1], [0], [1], [2], [3], [4], \dots \}. \]

This simplifies to:

\[ \mathbb{Z}_3 = \{ [0], [1], [2] \} \quad = \quad \{ [-1], [0], [1] \}. \]

Theorem

\[ \mathbb{Z}_n = \{ [0], [1], [2], \dots, [n-1] \}. \]

Example (Where \( n = 3 \))

The mapping \( \pi \) is always surjective and never injective.