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\in \mathbb{Z}\text{,}\) \(a\equiv a\) (mod \(n\)).
If \(a\equiv b\) (mod \(n\)), then \(b\equiv a\) (mod \(n\)).
If it happens that both \(a\equiv b\) and \(b\equiv c\) (mod \(n\)), then \(a\equiv 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\)).
(Symmetric) If \(a\equiv b\) (mod \(n\)), then \(b\equiv a\) (mod \(n\)).
(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\equiv c\) and \(b\equiv d\) (modulo some fixed modulus \(n\)), then both of these congruences hold:
\(\displaystyle a+b\equiv c+d\)
\(\displaystyle ab\equiv 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{.}\)
The impact of the previous result is that if I want to do a computation, I can pick any number with the same remainder modulo \(n\text{,}\) and the computation will get the same answer. (Hopefully I pick an easier number to work with!) Here is an example.
Example 4.3.3.
We collate examples of both propositions here. As an example of what
Proposition 4.3.1 implies,
\(2\equiv 5\) (mod
\(n\)) is the same thing as saying
\(5\equiv 2\) (mod
\(n\)). Then transitivity (and a careful use of contradiction) would imply that if
\(2\not\equiv 6\) (mod
\(n\)), then
\(5\not\equiv 6\) (mod
\(n\)) either.
More interesting are examples of
Proposition 4.3.2. A basic one is to replace computing
\(2\cdot 2\cdot 2\cdot 2\) modulo
\(3\) by the choice
\(-1\cdot -1\cdot -1\cdot -1\) instead, getting the same answer (modulo
\(3\)). More impressive might be, instead of adding
\(16+15\) modulo
\(17\text{,}\) to compute instead
\(-1+(-2)=-3\) in the same modulus.
It won’t always be that clear-cut, but that is the general idea.
