Definition 4.7.
Let \(n\in\N\text{,}\) and let \(a, b\in\Z\text{.}\) The number \(a\) is congruent to the number \(b\) modulo \(n\text{,}\) denoted \(a \equiv b (mod n)\text{,}\) if \(a - b = kn\) for some \(k\in\Z\text{.}\)
Section 4.2 Congruence
Example 4.8.
We see that \(19 \equiv -5 (mod 4)\text{,}\) because \(19 - (-5) = 24 = 6 · 4\text{;}\) and \(7 \equiv 7 (mod 3)\text{,}\) because \(7 - 7 = 0 = 0 · 3\text{;}\) and \(13 \not\equiv 2 (mod 9)\text{,}\) because \(13 - 2 = 11\) and \(11\) is not a multiple of \(9\text{.}\)
Lemma 4.9.
Let \(\n\in N\text{,}\) and let \(a, b, c\in\Z\text{.}\)
- \(a \equiv a (mod n)\text{.}\)
- If \(a \equiv b (mod n)\) then \(b \equiv a (mod n)\text{.}\)
- If \(a \equiv b (mod n)\) and \(b \equiv c (mod n)\text{,}\) then \(a \equiv c (mod n)\text{.}\)
Proof.
- Observe that\(a - a = 0 · n\text{.}\)
- Suppose that \(a \equiv b (mod n)\text{.}\) Then \(a-b = kn\) for some \(k\in\Z\text{.}\) Hence \(b-a = (-k)n\text{.}\) Because \(-k\in\Z\text{,}\) it follows that \(b \equiv a (mod n)\text{.}\)
- Suppose that \(a \equiv b (mod n)\) and \(b \equiv c (mod n)\text{.}\) Then \(a-b = kn\) and \(b-c = jn\) for some \(k, j\in\Z\text{.}\) Adding these two equations we obtain \(a-c = (k + j)n\text{.}\) Because \(k + j\in\Z\text{,}\) it follows that \(a \equiv c (mod n)\text{.}\)
Theorem 4.10.
Let \(n\in\N\text{,}\) and let \(a\in\Z\text{.}\) Then there is a unique \(r\in\{0, \dots, n - 1\}\) such that \(a \equiv r (mod n)\text{.}\)
Proof.
To prove uniqueness, suppose that there are \(x, y\in\{0, \dots, n - 1\}\) such that \(a \equiv x (mod n)\) and \(a \equiv y (mod n)\text{.}\) It follows from Lemma 5.2.3 (2) that \(x \equiv a (mod n)\text{,}\) and from Lemma 5.2.3 (3) that \(x \equiv y (mod n)\text{.}\) That is, we have \(x - y = pn\) for some \(p\in\Z\text{.}\) On the other hand, because \(x, y\in\{0, \dots, n - 1\}\text{,}\) it follows that \(-(n - 1) \leq x - y \leq n - 1\text{.}\) We deduce that \(p = 0\text{,}\) and hence that \(x = y\text{.}\) To prove existence, we use the Division Algorithm (Theorem A.5) to deduce that there are \(q, r\in\Z\) such that \(a = nq + r\) and \(0 \leq r < n\text{.}\) Hence \(a - r = qn\text{,}\) and therefore \(a \equiv r (mod n)\text{.}\)
Corollary 4.11.
Let \(n\in\N\text{,}\) and let \(a\in\Z\text{.}\) Then precisely one of the following holds: either \(a = nk\) for some \(k\in\Z\text{,}\) or \(a = nk + 1\) for some \(k\in\Z\text{,}\) or \(a = nk + 2\) for some \(k\in\Z\text{,}\) \dots, or \(a = nk + (n - 1)\) for some \(k\in\Z\text{.}\)
Corollary 4.12.
Let \(a\in\Z\text{.}\) Then \(a\) is even or odd, but not both.
Theorem 4.13.
Let \(n\in\N\text{.}\)
- Let \(a, b\in\Z\text{.}\) If \(a \equiv b (mod n)\text{,}\) then \([a] = [b]\text{.}\) If \(a \not\equiv b (mod n)\text{,}\) then [\(a] \cap [b] = \es\text{.}\)
- \([0] \cup [1] \cup\dots\cup [n - 1] = \Z\text{.}\)
Proof.
-
Suppose that \(a \equiv b (mod n)\text{.}\) Let \(x\in [a]\text{.}\) Then by the definition of relation classes we know that \(a \equiv x (mod n)\text{.}\) By Lemma 5.2.3 (2) it follows that \(b \equiv a (mod n)\text{,}\) and hence by Lemma 5.2.3 (3) we deduce that \(b \equiv x (mod n)\text{.}\) Therefore \(x\in [b]\text{,}\) and hence \([a] \subseteq [b]\text{.}\) A similar argument shows that \([b] \subseteq [a]\text{.}\) We conclude that \([a] = [b]\text{.}\)Now assume that \(a \not\equiv b (mod n)\text{.}\) We use proof by contradiction. Suppose that \([a] \cap [b] \neq \es\text{.}\) Hence there is some \(y\in [a] \cap [b]\text{.}\) Then \(y\in [a]\) and \(y\in [b]\text{,}\) so that \(a \equiv y (mod n)\) and \(b \equiv y (mod n)\text{.}\) By Lemma 5.2.3 (2) we see that \(y \equiv b (mod n)\text{,}\) and by Lemma 5.2.3 (3) it follows that \(a \equiv b (mod n)\text{,}\) which is a contradiction. We conclude that \([a] \cap [b] = \es\text{.}\)
- By definition \([a] \subseteq Z\) for all \(a\in\Z\text{,}\) and therefore [\(0] \cup\dots\cup [n - 1] \subseteq\Z\text{.}\) Let \(x\in\Z\text{.}\) By Theorem 5.2.4 there is a unique \(r\in\{0, \dots, n-1\}\) such that \(x \equiv r (mod n)\text{.}\) It follows from Lemma 5.2.3 (2) that \(r \equiv x (mod n)\text{.}\) Hence \(x\in [r]\text{.}\) Because \(r\in\{0, \dots, n - 1\}\text{,}\) it follows that \(x\in [0] \cup\dots\cup [n - 1]\text{.}\) Therefore \(\Z \subseteq [0] \cup\dots\cup [n - 1]\text{.}\) We conclude that \([0] \cup\dots\cup [n - 1] = \Z\text{.}\)
Definition 4.14.
Let \(n\in\N\text{.}\) The set of integers modulo \(n\text{,}\) denoted \(\Z/n\text{,}\) is the set defined by \(\Z/n = \{[0], [1], \dots, [n - 1]\}\text{,}\) where the relation classes are for congruence modulo \(n\text{.}\)
Convention 4.15.
The set \(\Z/n\) is also denoted \(\Z/n\Z\) in some texts, for reasons that will become apparent if the reader learns about group theory.
Example 4.16. Like Clockwork.
The integers modulo \(12\) is the set \(\Z/12 = \{[0], [1], \dots, [11]\}\text{.}\) This set has \(12\) elements, each of which is itself a set (namely, a relation class), but which is viewed here as a single element in the set \(\Z/12\text{.}\) The relation classes in \(\Z/12\) could each be described differently. For example, we see that \([0] = [12]\text{,}\) and so \(\Z/12 = \{[12], [1], \dots, [11]\}\text{,}\) which is what we see on the face of a clock. For mathematical purposes it is more convenient to write \([0]\) rather than \([12]\text{,}\) and so we will continue to write \(\Z/12\) as we did originally; it would also be nice to have the \(12\) on clocks replaced with \(0\text{,}\) but historical practice holds sway over mathematics in this situation. There are, of course, many other ways to rewrite the elements of \(\Z/12\text{,}\) for example \(\Z/12 = \{[-36], [25], [-10], \dots, [131]\}\text{,}\) and so it would in principle be possible to replace the number on a clock with \(-36, 25, -10, \dots, 131\text{,}\) though presumably only mathematicians would find that amusing.
Definition 4.17.
Let \(n\in\N\text{.}\) Let \(+\) and \(·\) be the binary operations on \(\Z\n\) defined by \([a] + [b] = [a + b]\) and \([a] · [b] = [ab]\) for all \([a], [b]\in\Z/n\text{.}\)
Lemma 4.18.
Let \(n\in\N\text{,}\) and let \(a, b, c, d\in\Z\text{.}\) Suppose that \(a \equiv c (mod n)\) and \(b \equiv d (mod n)\text{.}\) Then \(a + b \equiv c + d (mod n)\) and \(ab \equiv cd (mod n)\text{.}\)
Proof.
There exist \(k, j\in\Z\) such that \(a - c = kn and b - d = jn\text{.}\) Then \(a = c + kn\) and\(b = d + jn\text{,}\) and therefore a + b = (c + kn) + (d + jn) = c + d + (k + j)n, ab = (c + kn)(d + jn) = cd + (c j + dk + k jn)n. The desired result now follows.
Theorem 4.19.
Let \(n\in\N\text{,}\) and let \([a], [b], [c], [d]\in\Z/n\) . Suppose that \([a] = [c]\) and \([b] = [d]\text{.}\) Then \([a + b] = [c + d]\) and \([ab] = [cd]\text{.}\)
Definition 4.20.
Let \(n\in\N\text{.}\) The canonical map for congruence modulo \(n\) is the function \(\gamma : \Z \to\Z/n\) defined by \(\gamma (a) = [a]\) for all \(a\in Z\text{.}\)
Convention 4.21.
Observe that there is a distinct function \(\gamma \) for each \(n\in\N\text{,}\) but to avoid unnecessarily cumbersome notation (such as \(\gamma _n\)), we will assume that the number \(n\) is always known from the context.
Remark 4.22.
The canonical map \(\gamma : \Z \to\Z/n\) is a special case of a more general type of canonical map that will be seen in Definition 5.3.8.
Exploration 4.23.
Let \(n\in\N\text{,}\) and let \(a, b\in\Z\text{.}\) Then \(\gamma (a+b) = \gamma (a)+\gamma (b)\) and \(\gamma (ab) =\gamma (a) · \gamma (b)\text{.}\)
