Section5.3Properties of Congruence
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.
Proposition5.3.1Congruence is an equivalence relation
Congruence is reflexive, symmetric, and transitive. That is, all the things you know are true about equality are also true about congruence (with a particular modulus \(n\) picked, of course).
- 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.
Proof
- For any \(a\in \mathbb{Z}\), \(a\equiv a\) mod (\(n\)).
- The definition of congruence means we want to show \(n\mid (a-a)\).
- But \(a-a=0\). So we claim \(n\mid 0\).
- Any questions?
- 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.
- 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)\).
Proposition5.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 \(n\)):
- \(a+b\equiv c+d\)
- \(ab\equiv cd\)
Proof
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 they have the same remainder modulo \(n\).
- \(ab\equiv cd\)
Combine this with what one should already know about equivalence relations, and we are ready to roll. Why?
The relation properties mean that we can divide up all integers into "equivalence classes". That is, \(\mathbb{Z}\) can be broken up into disjoint pieces which we are free to consider as units, and which stay different.
The fact that equivalence classes for equivalence relations partition the set is assumed as background knowledge. As for well-definedness, it means that 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.
Example5.3.3
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.
It won't always be that clear-cut, but that is the general idea.
