Skip to main content

PLP An introduction to mathematical proof

Seçkin Demirbaş, Andrew Rechnitzer

Section 5.3 Congruence modulo \(n\)

Many results about divisibility of integers involve a fair bit of tedious work involving proof by cases; Result 5.2.5 is a good example of this. In that case we are interested in divisibility by 3 and so we use Euclidean division to separate the integers into 3 cases depending on their remainder. Much of that work can be simplified by introducing congruence.
🔗

Definition 5.3.1.

Let \(a,b \in \mathbb{Z}\) and \(n \in \mathbb{N}\text{.}\) We say that \(a\) is congruent to \(b\) modulo \(n\) when \(n\mid(a-b)\text{.}\) The “n” is refered to as the modulus and we write the congruence as \(a \equiv b \mod n\text{.}\)
🔗
When \(n \nmid (a-b)\) we say that \(a\) is not congruent to \(b\) modulo \(n\text{,}\) and write \(a \not\equiv b \mod n\text{.}\)
🔗
🔗
Some simple examples:
  • \(19\) is congruent to \(5\) modulo 7, since \(19-5=14 = 2(7)\text{,}\)
    🔗
  • \(11\) is congruent to \(27\) modulo 4, since \(11-27 = -16 = 4(-4)\text{,}\) and
    🔗
  • \(13\) is not congruent to \(7\) modulo 5 since \(13-7=6\) and \(5 \nmid 6\text{.}\)
    🔗
Also notice that congruence nicely extends parity; we can re-express parity as just congruence modulo 2.
🔗

Proof.

We prove both implications in turn. So start by assuming that \(a \equiv b \mod 2\text{.}\) Then we know that \(2 \mid (a-b)\) and thus \(a-b=2k\) for some \(k \in \mathbb{Z}\text{.}\) Now either \(a\) is even or odd.
  • When \(a\) is even, we know that \(a=2\ell\) for some integer \(\ell\text{,}\) and thus \(b=2\ell-2k\) and so is also even.
    🔗
  • Similarly when \(a\) is odd, we know that \(a=2m+1\) for some integer \(m\text{,}\) and thus \(b=2m-2k+1\) and so is also odd.
    🔗
Thus being congruent modulo 2 implies that they have the same parity.
🔗
Now assume that \(a,b\) have the same parity. Then either they are both even or they are both odd.
  • When \(a,b\) are both even, we can write \(a=2k, b=2\ell\) and so \(a-b = 2(k-\ell)\text{.}\)
    🔗
  • When \(a,b\) are both odd, we can write \(a=2k+1, b=2\ell+1\) and so \(a-b = 2(k-\ell)\text{.}\)
    🔗
In both cases the difference \(a-b\) is divisible by 2 and so \(a \equiv b \mod 2\) as required.
🔗
🔗
Perhaps the main reason that congruence modulo \(m\) is so important is that congruence interacts very nicely with basic arithmetic operations. This gives rise to what is known as modular arithmetic.
🔗

Proof.

Let \(n \in \mathbb{N}\text{,}\) and let \(a,b,c,d \in \mathbb{Z}\) so that \(a \equiv c \mod n\) and \(b \equiv d \mod n\text{.}\) Hence \(a=c+nk, b=d+n\ell \) where \(k,\ell\) are integers.
  • We can write \((a+b) = (c+d) + n(k+\ell)\text{,}\) so \((a+b)-(c+d)=n(k+\ell)\text{.}\) Hence \((a+b) \equiv (c+d) \mod n\text{.}\)
    🔗
  • Similarly, we can write \((a-b) = (c-d) + n(k-\ell)\text{,}\) so \((a-b)-(c-d)=n(k-\ell)\text{.}\) Hence \((a-b) \equiv (c-d) \mod n\text{.}\)
    🔗
  • Now \(ab = (c+nk)(d+n\ell) = cd + n(dk+c\ell) + n^2kl\text{.}\) So \(ab-cd = n(dk+c\ell + nkl)\text{,}\) and hence \(ab \equiv cd \mod n\text{.}\)
    🔗
🔗
🔗
We can now use this result to simplify some of our proof-by-cases proofs. Let’s start by reproving Result 5.2.5. And we start that by restating the result in terms of congruences:
🔗

Another proof of Result 5.2.5.

We start by restating the result in terms of congruences:
\begin{equation*} n \equiv 0 \mod 3 \iff n^2 \equiv 0 \mod 3, \end{equation*}
and now we prove each implication in turn
  • Assume that \(n \equiv 0 \mod 3\text{,}\) then by Theorem 5.3.3 we know that \(n^2 \equiv 0 \mod 3\) as required.
    🔗
  • We prove the contrapositive of the reverse implication, so assume that \(n \not\equiv 0 \mod 3\text{.}\) Thus either \(n \equiv 1 \mod 3\) or \(n \equiv 2 \mod 3\text{.}\)
    • When \(n \equiv 1 \mod 3\text{,}\) Theorem 5.3.3 tells us that \(n^2 \equiv 1 \mod 3\text{.}\)
      🔗
    • Similarly, when \(n \equiv 2 \mod 3\text{,}\) we know that \(n^2 \equiv 4 \mod 3\text{.}\) And since \(4 \equiv 1 \mod 3\text{,}\) this means that \(n^2 \equiv 1 \mod 3\text{.}\)
      🔗
    So in both cases, \(n^2 \not\equiv 0 \mod 3\) as required.
    🔗
    🔗
🔗
🔗
Notice we are doing something a little sneaky in the proof. We deduced that since \(n^2 \equiv 4 \mod 3\) and \(4 \equiv 1 \mod 3\text{,}\) we know that \(n^2 \equiv 1 \mod 3\text{.}\) This is because congruence is transitive — a notion we will return to in Chapter 9. But since it is quite useful, let’s prove it now.
🔗

Proof.

Let \(a,b,c\) and \(n\) be as stated. Then we know that for some \(k,\ell\in\mathbb{Z}\)
\begin{equation*} a-b = nk \qquad \text{and} \qquad b-c = n \ell. \end{equation*}
Then \((a-b)+(b-c)=a-c = n(k+\ell)\) and so \(a \equiv c \mod n\text{.}\)
🔗
🔗
Here is another example; congruence makes this easier to prove.
🔗

Proof.

Let \(3 \nmid a\) and \(3 \nmid b\text{.}\) Then, by Euclidean division, we know that \(a \equiv 1 \mod 3\) or \(a \equiv 2 \mod 3\text{.}\)
  • When \(a \equiv 1 \mod 3\text{,}\) \(a^2 \equiv 1 \mod 3\text{.}\)
    🔗
  • And, when \(a \equiv 2 \mod 3\text{,}\) \(a^2 \equiv 4 \mod 3\text{.}\) Since \(4 \equiv 1 \mod 3\text{,}\) we also have that \(a^2 \equiv 1 \mod 3\text{.}\)
    🔗
So in either case \(a^2 \equiv 1 \mod 3\text{.}\) This also implies that \(b^2 \equiv 1 \mod 3\text{.}\) Thus \(a^2 - b^2 \equiv 0 \mod 3\text{.}\) So finally we can conclude that \(3 \mid (a^2-b^2)\) as required.
🔗
🔗
We will return to congruences and modular arithmetic in Section 9.4, but now we turn to a very famous inequality.
🔗
🔗
PrevTopNext