Some proofs in this section will require a basic understanding of modular arithmetic and congruences. Here are some of the important properties and theorems. Their proofs can be found here.
Congruences
Let m be a natural number including 0, and let a and b be integers. Then a ≡ b (mod m) if and only if m|(a-b) and “a is congruent to b modulo m”.
Basic Properties
If m is a natural number (not including 0) then the following properties are satisfied for any integral a, b, and c.
1.) reflexivity: a≡ a (mod m).
2.) symmetry: If a ≡ b (mod m), then b ≡ a (mod m).
3.) transitivity: If a ≡ b (mod m) and b ≡ c (mod m), then a ≡ c (mod m).
Theorem 1
Let m be a natural number (not including 0) and a, b, c, and d be integers. If a≡b (mod m) and c≡ d (mod m), then
1.) a+c ≡ b+d (mod m)
2.) a-c ≡ b-d (mod m)
3.) a×c ≡ b×d (mod m)
Theorem 2
Let m be a natural number (not including 0) and a, b, c, and d be integers. If a×b ≡ a×c (mod m) and a and m are relatively prime, then b≡c (mod m).
Theorem 3
Let m be a natural number (not including 0) and a, b, and c be integers. If a≡b (mod m), then an≡bn (mod m) for any positive integer n.