# congruence

One 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
ab (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 ab (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, aa (mod m),
• The symmetric property: If ab (mod m), then ba (mod m),
• The transitive property: If ab (mod m) and bc (mod m), then ac (mod m).
Because of these three properties, we know the set of integers is divided into m different congruence classes modulo m.

If a, b, c and d are any integers with ab (mod m) and cd (mod m), then

• a + cb + d (mod m)
• a - cb - d (mod m)
• acbd (mod m)
• If gcd(c,m) ≡ 1 and acbc (mod m), then ab (mod m)