There are two main sets of propositions that make this possible. The proofs are not hard, and you may skip them on a first reading.
Proposition4.3.1Congruence is an equivalence relation
Congruence is reflexive, symmetric, and transitive, which combine to make it an equivalence relation.
For any \(a\in \mathbb{Z}\), \(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).
We will show each of the properties, leaving some pieces to the reader (Exercise 4.7.6).
-
(Reflexive) For any \(a\in \mathbb{Z}\), \(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)\), 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}\).
Add these two equations to get \(a-c=n(k+\ell)\), which is the definition of \(n\mid (a-c)\).
Proposition4.3.2Congruence arithmetic is well-defined
Congruence is well-defined with respect to addition and multiplication. That is, if \(a\equiv c\) and \(b\equiv d\) (modulo some fixed modulus \(n\)):
\(a+b\equiv c+d\)
\(ab\equiv cd\)
Let \(a\equiv c\) and \(b\equiv d\) (modulo some fixed \(n\)):
-
\(a+b\equiv c+d\)
There must exist \(k\) and \(\ell\) such that \(a=c+kn\) and \(b=d+\ell n\).
So \(a+b=c+kn+d+\ell n=(c+d)+(k+\ell)n\).
So \(a+b\) and \(c+d\) must have the same remainder modulo \(n\).
-
\(ab\equiv cd\)
Just below, in Section 4.4, we will see that these propositions and the following fact mean we are ready to roll with modulo and integers.
Fact4.3.3
Any set that has an equivalence relation on it can be broken up into disjoint subsets called equivalence classes. It can be useful to considered these classes as elements of a set of all such classes.
We consider this to be background; see any intro-to-proof text.
So we can break up \(\mathbb{Z}\) into disjoint subsets, and use well-definedness. If I want to do a computation, I can pick any number with the same remainder modulo \(n\), and it will still work fine. (Hopefully I pick an easier number to work with!) Here is an example.
Example4.3.4
For instance, \(2\equiv 5\) (mod \(n\)) is the same thing as saying \(5\equiv 2\) (mod \(n\)), and if \(2\not\equiv 6\) (mod \(n\)), then \(5\not\equiv 6\) (mod \(n\)) either.
Or instead of computing \(2\cdot 2\cdot 2\cdot 2\) modulo \(3\), I might choose \(-1\cdot -1\cdot -1\cdot -1\) instead, getting the same answer (modulo 3)
It won't always be that clear-cut, but that is the general idea.
