congruence
(another Prime Pages' Glossary entries)
The Prime Glossary
Glossary: Prime Pages: Top 5000:
The hardware and software on this system was updated September 4th.  Please let me know of any problem you encounter. <caldwell@utm.edu>

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

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).
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 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


Chris K. Caldwell © 1999-2014 (all rights reserved)