This site will be down for maintenance beginning noon CDT (5pm UTC) Wed April 14

# 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

**if**

*a*is congruent to*b*modulo*m**m*divides

*a*-

*b*. We write this as

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.a≡b(modm).

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

*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*)*a**c*≡*b**d*(mod*m*)- If gcd(
*c*,*m*) ≡ 1 and*a**c*≡*b**c*(mod*m*), then*a*≡*b*(mod*m*)

**See Also:** Residue

Printed from the PrimePages <primes.utm.edu> © Chris Caldwell.