Congruence

If $b-c$ is integrally divisible by $a$, then $b$ and $c$ are said to be congruent with Modulus $a$. This is written mathematically as $b\equiv c$ (mod $a$). If $b-c$ is not divisible by $a$, then we say $b\not\equiv c$ (mod $a$). The (mod $a$) is sometimes omitted when the Modulus $a$ is understood for a given computation, so care must be taken not to confuse the symbol $\equiv$ with that for an Equivalence. The quantity $b$ is called the Residue or Remainder. The Common Residue is taken to be Nonnegative and smaller than $m$, and the Minimal Residue is $b$ or $b-m$, whichever is smaller in Absolute Value. In many computer languages (such as FORTRAN or Mathematica ${}^{\scriptstyle\circledRsymbol}$), the Common Residue of $c$ (mod $a$) is written mod(c,a).

Congruence arithmetic is perhaps most familiar as a generalization of the arithmetic of the clock: 40 minutes past the hour plus 35 minutes gives $40+35\equiv 15\ \left({{\rm mod\ } {60}}\right)$, or 15 minutes past the hour, and 10 o'clock a.m. plus five hours gives $10+5\equiv 3\ \left({{\rm mod\ } {12}}\right)$, or 3 o'clock p.m. Congruences satisfy a number of important properties, and are extremely useful in many areas of Number Theory. Using congruences, simple Divisibility Tests to check whether a given number is divisible by another number can sometimes be derived. For example, if the sum of a number's digits is divisible by 3 (9), then the original number is divisible by 3 (9).

Congruences also have their limitations. For example, if $a\equiv b$ and $c\equiv d\ \left({{\rm mod\ } {n}}\right)$, then it follows that $a^x\equiv b^x$, but usually not that $x^c\equiv x^d$ or $a^c\equiv b^d$. In addition, by ``rolling over,'' congruences discard absolute information. For example, knowing the number of minutes past the hour is useful, but knowing the hour the minutes are past is often more useful still.

Let $a\equiv a'\ \left({{\rm mod\ } {m}}\right)$ and $b\equiv b'\ \left({{\rm mod\ } {m}}\right)$, then important properties of congruences include the following, where $\Rightarrow$ means ``Implies'':

1. Equivalence: $a\equiv b\ \left({{\rm mod\ } {0}}\right) \Rightarrow a=b$.

2. Determination: either $a\equiv b\ \left({{\rm mod\ } {m}}\right)$ or $a \not\equiv b\ (\rm {mod\ }m)$.

3. Reflexivity: $a\equiv a\ \left({{\rm mod\ } {m}}\right)$.

4. Symmetry: $a\equiv b\ \left({{\rm mod\ } {m}}\right) \Rightarrow b\equiv a\ \left({{\rm mod\ } {m}}\right)$.

5. Transitivity: $a\equiv b\ \left({{\rm mod\ } {m}}\right)$ and $b\equiv c\ \left({{\rm mod\ } {m}}\right) \Rightarrow a\equiv c\ \left({{\rm mod\ } {m}}\right)$.

6. $a+b\equiv a'+b'\ \left({{\rm mod\ } {m}}\right)$.

7. $a-b\equiv a'-b'\ \left({{\rm mod\ } {m}}\right)$.

8. $ab\equiv a'b'\ \left({{\rm mod\ } {m}}\right)$.

9. $a\equiv b\ \left({{\rm mod\ } {m}}\right) \Rightarrow ka\equiv kb\ \left({{\rm mod\ } {m}}\right)$.

10. $a\equiv b\ \left({{\rm mod\ } {m}}\right) \Rightarrow a^n\equiv b^n\ \left({{\rm mod\ } {m}}\right)$.

11. $a\equiv b\ \left({{\rm mod\ } {m_1}}\right)$ and $a\equiv b\ \left({{\rm mod\ } {m_2}}\right) \Rightarrow a\equiv b\ \left({{\rm mod\ } {[m_1,m_2]}}\right)$, where $[m_1,m_2]$ is the Least Common Multiple.

12. $ak\equiv bk\ \left({{\rm mod\ } {m}}\right) \Rightarrow a\equiv b\ \left({{\rm mod\ } {m\over(k,m)}}\right)$, where $(k,m)$ is the Greatest Common Divisor.

13. If $a\equiv b\ \left({{\rm mod\ } {m}}\right)$, then $P(a)\equiv P(b)\ \left({{\rm mod\ } {m}}\right)$, for $P(x)$ a Polynomial.

Properties (6-8) can be proved simply by defining

$$a \equiv a'+rd$$ (1)

$$b \equiv b'+sd,$$ (2)

where $r$ and $s$ are Integers. Then

$$a+b = a'+b'+(r+s)d$$ (3)

$$a-b = a'-b'+(r-s)d$$ (4)

$$ab = a'b'+(a's+b'r+rsd)d,$$ (5)

so the properties are true.

Congruences also apply to Fractions. For example, note that

$$2\times 4 \equiv 1 \qquad 3\times 3\equiv 2 \qquad 6\times 6\equiv 1 {\rm\ (mod\ } 7),$$ (6)

so

$${\textstyle{1\over 2}}\equiv 4\qquad {\textstyle{1\over 4}}\... ...equiv 3\qquad {\textstyle{1\over 6}}\equiv 6 {\rm\ (mod\ } 7).$$ (7)

To find $p/q$ mod $m$, use an Algorithm similar to the Greedy Algorithm. Let $q_0\equiv q$ and find

$$p_0=\left\lceil{m\over q_0}\right\rceil ,$$ (8)

where $\left\lceil{x}\right\rceil$ is the Ceiling Function, then compute

$$q_1\equiv q_0 p_0 {\rm\ (mod\ } m).$$ (9)

Iterate until $q_n=1$, then

$${p\over q} \equiv p \prod_{i=0}^{n-1} p_i {\rm\ (mod\ } m).$$ (10)

This method always works for $m$ Prime, and sometimes even for $m$ Composite. However, for a Composite $m$, the method can fail by reaching 0 (Conway and Guy 1996).

A Linear Congruence

$$ax\equiv b\ \left({{\rm mod\ } {m}}\right)$$ (11)

is solvable Iff the congruence

$$b\equiv 0\ \left({{\rm mod\ } {(a,m)}}\right)$$ (12)

is solvable, where $d\equiv (a,m)$ is the Greatest Common Divisor, in which case the solutions are $x_0$, $x_0+m/d$, $x_0+2m/d$, ..., $x_0+(d-1)m/d$, where $x_0 < m/d$. If $d=1$, then there is only one solution.

A general Quadratic Congruence

$$a_2x^2+a_1x+a_0\equiv 0\ \left({{\rm mod\ } {n}}\right)$$ (13)

can be reduced to the congruence

$$x^2\equiv q\ \left({{\rm mod\ } {p}}\right)$$ (14)

and can be solved using Excludents. Solution of the general polynomial congruence

$$a_mx^m+\ldots+a_2x^2+a_1x+a_0\equiv 0\ \left({{\rm mod\ } {n}}\right)$$ (15)

is intractable. Any polynomial congruence will give congruent results when congruent values are substituted.

Two simultaneous congruences

$$x\equiv a\ \left({{\rm mod\ } {m}}\right)$$ (16)

$$x\equiv b\ \left({{\rm mod\ } {n}}\right)$$ (17)

are solvable only when $a\equiv b\ \left({{\rm mod\ } {(m,n)}}\right)$, and the single solution is

$$x\equiv x_0\ \left({{\rm mod\ } {[m,n]}}\right),$$ (18)

where $x_0 < m/d$.

See also Cancellation Law, Chinese Remainder Theorem, Common Residue, Congruence Axioms, Divisibility Tests, Greatest Common Divisor, Least Common Multiple, Minimal Residue, Modulus (Congruence), Quadratic Reciprocity Law, Residue (Congruence)

References

Conway, J. H. and Guy, R. K. ``Arithmetic Modulo $p$.'' In The Book of Numbers. New York: Springer-Verlag, pp. 130-132, 1996.

Courant, R. and Robbins, H. ``Congruences.'' §2 in Supplement to Ch. 1 in What is Mathematics?: An Elementary Approach to Ideas and Methods, 2nd ed. Oxford, England: Oxford University Press, pp. 31-40, 1996.

Shanks, D. Solved and Unsolved Problems in Number Theory, 4th ed. New York: Chelsea, p. 55, 1993.

Weisstein, E. W. ``Fractional Congruences.'' Mathematica notebook ModFraction.m.