Section 4.3 Properties of Congruence
There are two main sets of propositions that make arithmetic with congruences possible. The proofs are not hard, and you may skip them on a first reading.Proposition 4.3.1. Congruence is an equivalence relation.
Congruence is reflexive, symmetric, and transitive, which are the conditions for it to be an equivalence relation.
For any a∈Z, a≡a (mod n).
If a≡b (mod n), then b≡a (mod n).
If it happens that both a≡b and b≡c (mod n), then a≡c (mod n) as well.
See any intro-to-proof text for more background. For our purposes, this means all the things you know are true about equality are also true about congruence (with a particular modulus n picked, of course).
Proof.
We will show each of the properties, leaving some pieces to the reader (Exercise 4.7.9).
-
(Reflexive) For any \(a\in \mathbb{Z}\text{,}\) \(a\equiv a\) (mod \(n\)).
The definition of congruence means we want to show \(n\mid (a-a)\text{.}\)
But \(a-a=0\text{.}\) So we claim \(n\mid 0\text{.}\)
Any questions?
-
(Symmetric) If \(a\equiv b\) (mod \(n\)), then \(b\equiv a\) (mod \(n\)).
For the reader!
-
(Transitive) If it happens that both \(a\equiv b\) and \(b\equiv c\) (mod \(n\)), then \(a\equiv c\) (mod \(n\)) as well.
The definition of congruence means we want to show if \(n\mid (a-b)\) and \(n\mid (b-c)\text{,}\) then \(n\mid (a-c)\) as well.
We use the definitions to see \(a-b=nk\) and \(b-c=n\ell\) for some \(k,\ell\in\mathbb{Z}\text{.}\)
Add these two equations to get \(a-c=n(k+\ell)\text{,}\) which is the definition of \(n\mid (a-c)\text{.}\)
Proposition 4.3.2. Congruence arithmetic is well-defined.
Addition and multiplication modulo n are well-defined. That is, if a≡c and b≡d (modulo some fixed modulus n), then both of these congruences hold:
a+b≡c+d
ab≡cd
Proof.
Let \(a\equiv c\) and \(b\equiv d\) (modulo some fixed \(n\)). We will prove that \(a+b\equiv c+d\) and then leave the proof that \(ab\equiv cd\) the reader in Exercise 4.7.10.
There must exist \(k\) and \(\ell\) such that \(a=c+kn\) and \(b=d+\ell n\text{.}\)
So \(a+b=c+kn+d+\ell n=(c+d)+(k+\ell)n\text{.}\)
So \(a+b\) and \(c+d\) must have the same remainder modulo \(n\text{.}\)
By definition then \(a+b\equiv c+d\text{.}\)
Example 4.3.3.
For instance, 2≡5 (mod n) is the same thing as saying 5≡2 (mod n), and if 2≢6 (mod n), then 5≢6 (mod n) either.
Or instead of computing 2⋅2⋅2⋅2 modulo 3, I might choose −1⋅−1⋅−1⋅−1 instead, getting the same answer (modulo 3)