Suppose we have a natural number \(n\), then \((i \mod n)\) is the remainder after dividing \(n\) by \(i\). For example \((1 \mod 7) = (8 \mod 7) = (15 \mod 7) = 1\) and \((7 \mod 7) = 0\). From this we observe that for two numbers \(a\) and \(b\) to leave the same remainder, they need to be \(n\) numbers apart on the numbers line or in other words, \(|a - b|\) is a multiple of \(n\). Formally,

Definition 1.7.1
Given integers \(a\) and \(b\), and a natural number \(n\), we say that "\(a\) is congruent to \(b\) modulo \(n\)" and we write \(a \equiv b \mod n\) if \(a - b\) is divisible by \(n\).


This relation \(a \equiv b \mod n\) has the following properties:

Lemma 1.7.2
  1. For all \(a \in \mathbf{Z}\), \(a \equiv a \mod n\).
  2. For all \(a, b \in \mathbf{Z}\), \(a \equiv b \mod n\) if and only if \(b \equiv a \mod n\).
  3. For all \(a, b, c \in \mathbf{Z}\), if \(a \equiv b \mod n\) and \(b \equiv c \mod n\), then \(a \equiv c \mod n\).


Proof
For \((a)\), \(a - a = 0\) is divisible by \(n\). For \((b)\), if \(a - b\) is divisible by \(n\), then \(b - a\) is also divisible by \(n\) and vice versa. For \((c)\), if \(a - b\) is divisible by \(n\) and \(b - c\) is divisible by \(4n\), then \((a - b) + (b - c) = a - c\) is also divisible by \(n\). \(\ \blacksquare\)

Definition
For each integer \(a\), write $$ \begin{align*} [a] &= \{b \in \mathbf{Z} \ | \ a \equiv b \mod n\} \\ &= \{ a + kn \ | \ k \in \mathbf{Z} \} \end{align*} $$ The set \(a\) is called the residue class or congruence class of \(a\) modulo \(n\).
Also let \(rem_n(a)\) be the unique number \(r\) such that \(0 \leq r < n\) and \(a - r\) is divisible by \(n\). So it is the unique element of \([a]\) that lies in the interval \( \{0,1,...,n-1\} \).


Lemma 1.7.3
For \(a, b \in \mathbf{Z}\), the following are equivalent:
  1. \(a \equiv b \mod n\).
  2. \([a] = [b]\).
  3. \(\text{rem}_n(a) = \text{rem}_n(b)\).
  4. \([a] \cap [b] \neq \emptyset\).


Proof
\((a) \implies (b)\):
Suppose \(a \equiv b \mod n\). We want to show that \([a] = [b]\) by showing that \([a] \subseteq [b]\) and \([b] \subseteq [a]\). For any \(c \in \mathbf{Z}\), we know that if \(c \equiv a \mod n\), then \(c \equiv b \mod n\) by Lemma 1.7.2 (c). Therefore \([a] \subseteq [b]\). Similarly, if \(c \equiv b \mod n\), then \(c \equiv a \mod n\) and so \([a] = [b]\) as required.

\((b) \implies (c)\):
By definition, \(\text{rem}_n(x)\) is the unique element of \([x]\) that lies inside \(\{0,1,...,n-1\}\). So if \([a]=[b]\), then it must be the same element.

\((c) \implies (d)\):
\((d)\) is an immediate application of \((c)\)

\((d) \implies (a)\): Suppose that \([a] \cap [b] \neq \emptyset\). Let \(c \in [a] \cap [b]\). Then \(a \equiv c \mod n\) and \(b \equiv c \mod n\). But this implies that \(a \equiv b \mod n\). \(\ \blacksquare\)

Corollary 1.7.4
There exist exactly \(n\) distinct residue classes modulo \(n\) namely \([0], [1],...,[n-1]\). These classes are mutually disjoint.



Lemma 1.7.5
Let \(a, a', b, b'\) be integers with \(a \equiv a' \mod n\) and \(b \equiv b' \mod n\). Then \(a + b \equiv a' + b' \mod n\) and \(ab \equiv a'b' \mod n\)





References