Congruence arithmetic.
Lemma: If \(x\) and \(y\) are multiples of \(n\), so is \(x+y\).
Proposition: Given integers \(a\), \(b\), \(c\), and a natural number \(n\), if\(a\equiv b\pmod{n}\) then
- If \(c\equiv d\pmod{n}\), then \(a+c\equiv b+d\pmod{n}\)
- \(ac\equiv bc\pmod{n}\)
Congruence arithmetic continued
Proposition:
\(a^r\equiv b^r\pmod{n}\) for any natural number \(r\).