3 Congruences and modular arithmetic
3.1 Congruences
The following definition (originally due to Gauss) is a wonderful way of simplifying and organising lots of number-theoretic arguments:
Definition 3.1
Let \(a, b, m \in \mathbb{Z},\) with \(m \geqslant 1.\) We say “\(a\) is congruent to \(b\) modulo \(m\)” if \(m\) divides \(a - b\) (i.e. there exists \(k \in \mathbb{Z}\) such that \(a - b = k m\)).
Example 3.2
For example, \(a\) is congruent to 0 modulo 2 iff it’s even, and to 1 modulo 2 iff it’s odd.
It’s easy to see that, for a fixed \(m,\) this is an equivalence relation in \(a\) and \(b.\) So the equivalence classes (the congruence classes modulo \(m\)) form a partition of \(\mathbb{Z}\) into disjoint sets. There’s exactly \(m\) of these congruence classes, represented by the integers \(\{0, 1, \dots, m-1\},\) corresponding to the different remainders of \(a\) on division by \(m.\)
3.2 Modular arithmetic
Definition 3.3
We write \(\mathbb{Z}/ m\mathbb{Z}\) for the set of congruence classes modulo \(m.\)
You saw in M11 Algebra that this is a ring: the set \(m\mathbb{Z}\) of multiples of \(m\) is an ideal of \(\mathbb{Z},\) and \(\mathbb{Z}/ m\mathbb{Z}\) is the corresponding quotient ring. Moreover, the map \(\mathbb{Z}\to \mathbb{Z}/ m\mathbb{Z},\) sending \(a\) to its congruence class, is a ring homomorphism.
Remark 3.4
Take a moment to reflect on what this is really saying: it’s saying that, for \(a, b \in \mathbb{Z},\) the congruence classes of \(a \pm b\) and \(ab\) are uniquely determined by the congruence classes of \(a\) and \(b.\)
That might sound like a lot of abstract nonsense; but it’s actually immensely useful for solving concrete questions about \(\mathbb{Z}.\)
Example 3.5
“Do there exist integer solutions to the equation \(x^2 - 3y^2 = 2\)?”
Suppose \((x, y)\) was a solution. Then, reducing modulo \(3,\) we would have a solution to the equation \((x \bmod 3)^2 = 2\) in \(\mathbb{Z}/ 3\mathbb{Z}.\) But \(x \bmod 3\) must be one of \(\{0, 1, 2\},\) and we have \(0 ^2 = 0,\) \(1^2 = 2^2 = 1\) in \(\mathbb{Z}/ 3\mathbb{Z}.\) So there are no solutions.
Exercise 3.6
Show that if \(m, n \in \mathbb{N}_+\) with \(n \mid m,\) then there is a unique ring homomorphism \(\mathbb{Z}/ m\mathbb{Z}\to \mathbb{Z}/ n\mathbb{Z}\) sending the congruence class \(a + m\mathbb{Z}\) to \(a + n\mathbb{Z}\) for every \(a \in \mathbb{Z}.\)
3.3 Primes in congruence classes
Notice that if \(p\) is a prime, and \(p \ne 2,\) then \(p\) is odd, so \(p\) must be either \(1 \bmod 4\) (like 5) or \(3 \bmod 4\) (like 7).
Theorem 3.7
There are infinitely many primes \(p\) with \(p = 3 \bmod 4.\)
Proof. Suppose there are finitely many such primes, namely \(p_1, \dots, p_k\) (with \(p_1 = 3, p_2 = 7,\) etc). Consider the product \(N = 4 p_2 \dots p_k + 3\) (note \(p_1\) is not included!)
Clearly \(N\) can’t be divisible by any of the primes \(p_2, \dots, p_k,\) since these all divide \(4p_2\dots p_k\) but don’t divide 3. Moreover, it’s also not divisible by \(p_1 = 3\) either (since 3 doesn’t divide \(4p_2\dots p_k,\) but does divide 3). Finally, it is clearly odd and thus not divisible by 2 either. Hence all of its prime factors must be \(1 \bmod 4.\)
However, a product of numbers that are all \(1 \bmod 4\) must itself be \(1 \bmod 4,\) while \(N\) is obviously \(3 \bmod 4.\) So we have a contradiction.
Exercise 3.8
Why doesn’t this argument adapt to show that there are infinitely many primes which are \(1 \bmod 4\)?
Remark 3.9
This is a special case of a much more general theorem: for any \(a, b \in \mathbb{N}_+\) with \(\gcd(a, b) = 1,\) there are infinitely many primes \(p\) with \(p = a \bmod b\) (Dirichlet’s theorem on primes in arithmetic progressions.) However, this is a rather deep theorem and we won’t prove it in this module.
3.4 The Chinese remainder theorem
The next theorem will tell us that if \(m\) and \(n\) are coprime, then congruences mod \(m\) and congruences mod \(n\) are in some sense “independent of each other”: they give totally complementary information.
Theorem 3.10 • Chinese remainder theorem, or CRT
Let \(m, n \in \mathbb{N}_+\) be coprime, and let \(x, y \in \mathbb{Z}.\) Then there exist integers \(a\) such that \(a = x \bmod m\) and \(a = y \bmod n\); and the set of integers \(a\) with this property forms a congruence class modulo \(mn.\)
Remark 3.11
The theorem has this name because it was discovered by ancient Chinese mathematicians (long before it was known in Europe); there is a complete proof in Qin Jiushao’s Mathematical Treatise in Nine Sections from 1247.
Exercise 3.12
Find an integer \(a\) satisfying \(a = 5 \bmod 7\) and \(a = 6 \bmod 9.\)
Proof. Existence: We first show that there exist integers \(r, s\) with the following property:
\(r = 1 \bmod m\) and \(r = 0 \bmod n\);
\(s = 0 \bmod m\) and \(s = 1 \bmod n.\)
To see this, use Euclid’s algorithm to write \(1 = u m + v n.\) Then we can take \(r = v n,\) since \(v n = 1 - u m = 1 \bmod m\) and clearly \(v n = 0 \bmod n.\) Similarly, we can take \(s = u m.\) This proves the claim.
Having proved the claim, for any \(x, y\) we can take \(a = r x + s y.\)
Uniqueness: If \(a\) is one solution, then for any integer \(a',\) it follows that \(a'\) is a solution iff \(a - a'\) is divisible by both \(m\) and \(n.\) Since \(m\) and \(n\) are coprime, the set of integers that are divisible by both \(m\) and \(n\) is precisely the set of integers divisible by \(mn.\) So the set of solutions is precisely the congruence class of \(a \bmod mn,\) as claimed.
Remark 3.13
In more abstract language, we’ve shown that the natural map from \(\mathbb{Z}/ m n \mathbb{Z}\) to the direct product \((\mathbb{Z}/ m \mathbb{Z}) \times (\mathbb{Z}/ n \mathbb{Z})\) is a bijection. Since it’s also a ring homomorphism, these two rings are isomorphic.
Note that we can compute everything here explicitly, using Euclid’s algorithm applied to \((m, n)\) as the starting point.
In particular, if \(m = \prod_{i=1}^k p_i^{e_i}\) is the prime factorisation of \(m,\) then \[\mathbb{Z}/ m \mathbb{Z}\cong (\mathbb{Z}/ p_1^{e_1} \mathbb{Z}) \times \dots \times (\mathbb{Z}/ p_k^{e_k}\mathbb{Z}).\]