Skip to main content
Logo image

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.
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{.}\)
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.