congruenceOne of the most important tools in elementary number theory is modular arithmetic (or congruences). Suppose a, b and m are any integers with m not zero, then we say a is congruent to b modulo m if m divides a-b. We write this as
a ≡ b (mod m).For example: 6 ≡ 2 (mod 4), -1 ≡ 9 (mod 5), 1100 ≡ 2 (mod 9), and the square of any odd number is 1 modulo 8.
Congruences are found throughout our lives. For example, clocks work either modulo 12 or 24 for hours, and modulo 60 for minutes and seconds. Calendars work modulo 7 for days of the week and modulo 12 for months. The language of congruences was developed by Carl Friedrich Gauss in the early nineteenth century.
Notice a ≡ b (mod m) if and only if there is an integer q such that a = b + qm, so congruences can be translated to equalities with the addition of one unknown. Perhaps the three most important properties of congruences modulo m are:
- The reflexive property: If a is any integer, a ≡ a (mod m),
- The symmetric property: If a ≡ b (mod m), then b ≡ a (mod m),
- The transitive property: If a ≡ b (mod m) and b ≡ c (mod m), then a ≡ c (mod m).
If a, b, c and d are any integers with a ≡ b (mod m) and c ≡ d (mod m), then
- a + c ≡ b + d (mod m)
- a - c ≡ b - d (mod m)
- ac ≡ bd (mod m)
- If gcd(c,m) ≡ 1 and ac ≡ bc (mod m), then a ≡ b (mod m)
See Also: Residue