TOPICS
Search

Congruence


If two numbers b and c have the property that their difference b-c is integrally divisible by a number m (i.e., (b-c)/m is an integer), then b and c are said to be "congruent modulo m." The number m is called the modulus, and the statement "b is congruent to c (modulo m)" is written mathematically as

 b=c (mod m).
(1)

If b-c is not integrally divisible by m, then it is said that "b is not congruent to c (modulo m)," which is written

 b≢c (mod m).
(2)

The explicit "(mod m)" is sometimes omitted when the modulus m is understood by context, so in such cases, care must be taken not to confuse the symbol = with the equivalence sign.

The quantity b is sometimes called the "base," and the quantity c is called the residue or remainder. There are several types of residues. The common residue defined to be nonnegative and smaller than m, while the minimal residue is c or c-m, whichever is smaller in absolute value.

CongruenceClockMinutes

Congruence arithmetic is perhaps most familiar as a generalization of the arithmetic of the clock. Since there are 60 minutes in an hour, "minute arithmetic" uses a modulus of m=60. If one starts at 40 minutes past the hour and then waits another 35 minutes, 40+35=15 (mod 60), so the current time would be 15 minutes past the (next) hour.

CongruenceClockHours

Similarly, "hour arithmetic" on a 12-hour clock uses a modulus of m=12, so 10 o'clock (a.m.) plus five hours gives 10+5=3 (mod 12), 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=b and c=d (mod n), then it follows that a^x=b^x, but usually not that x^c=x^d or a^c=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=a^' (mod m) and b=b^' (mod m), then important properties of congruences include the following, where => means "implies":

1. Equivalence: a=b (mod 0)=>a=b (which can be regarded as a definition).

2. Determination: either a=b (mod m) or a≢b (mod m).

3. Reflexivity: a=a (mod m).

4. Symmetry: a=b (mod m)=>b=a (mod m).

5. Transitivity: a=b (mod m) and b=c (mod m)=>a=c (mod m).

6. a+b=a^'+b^' (mod m).

7. a-b=a^'-b^' (mod m).

8. ab=a^'b^' (mod m).

9. a=b (mod m)=>ka=kb (mod m).

10. a=b (mod m)=>a^n=b^n (mod m).

11. a=b (mod m_1) and a=b (mod m_2)=>a=b (mod [m_1,m_2]), where [m_1,m_2] is the least common multiple.

12. ak=bk (mod m)=>a=b (mod m/((k,m))), where (k,m) is the greatest common divisor.

13. If a=b (mod m), then P(a)=P(b) (mod m), for P(x) a polynomial.

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

a=a^'+rm
(3)
b=b^'+sm,
(4)

where r and s are integers. Then

a+b=a^'+b^'+(r+s)m
(5)
a-b=a^'-b^'+(r-s)m
(6)
ab=a^'b^'+(a^'s+b^'r+rsm)m,
(7)

so the properties are true.

Congruences also apply to fractions. For example, note that

 2×4=1    3×3=2    6×6=1 (mod 7),
(8)

so

 1/2=4    1/4=2    2/3=3    1/6=6 (mod 7).
(9)

To find p/q (mod m) where (q,m)=1 (i.e., q and m are relatively prime), use an algorithm similar to the greedy algorithm. Let q_0=q and find

 p_0=[m/(q_0)],
(10)

where [x] is the ceiling function, then compute

 q_1=q_0p_0 (mod m).
(11)

Iterate until q_n=1, then

 p/q=pproduct_(i=0)^(n-1)p_i (mod m).
(12)

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

Finding a fractional congruence is equivalent to solving a corresponding linear congruence equation

 ax=b (mod m).
(13)

A fractional congruence of a unit fraction is known as a modular inverse. A fractional congruence can be found in the Wolfram Language using the following function:

  FractionalMod[r_Rational, m_Integer] := Mod[
    Numerator[r]PowerMod[Denominator[r], -1, m], m]

or using the undocumented syntax PolynomialMod[r, m] for r an explicit rational number.


See also

Algebraic Congruence, Cancellation Law, Chinese Remainder Theorem, Common Residue, Congruence Axioms, Congruence Equation, Congruent, Divisibility Tests, Floor Function, Fractional Part, Functional Congruence, Geometric Congruence, Greatest Common Divisor, Integer Division, Least Common Multiple, Linear Congruence Equation, Minimal Residue, Mod, Modular Inverse, Modulus, Nearest Integer Function, Quadratic Congruence Equation, Quadratic Reciprocity Theorem, Quotient, Residue, RSA Encryption Explore this topic in the MathWorld classroom

Related Wolfram sites

http://functions.wolfram.com/IntegerFunctions/Mod/

Explore with Wolfram|Alpha

References

Burton, D. M. "The Theory of Congruences." Ch. 4 in Elementary Number Theory, 4th ed. Boston, MA: Allyn and Bacon, pp. 80-105, 1989.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.Hardy, G. H. and Wright, E. M. "Congruences and Classes of Residues," "Elementary Properties of Congruences," "Linear Congruences," "General Properties of Congruences," and "Congruences to Composite Moduli." §5.2-5.4 and Chs. 7-8 in An Introduction to the Theory of Numbers, 5th ed. Oxford, England: Clarendon Press, pp. 49-52 and 82-106, 1979.Hilton, P.; Holton, D.; and Pedersen, J. "A Far Nicer Arithmetic." Ch. 2 in Mathematical Reflections in a Room with Many Mirrors. New York: Springer-Verlag, pp. 25-60, 1997.Jones, G. A. and Jones, J. M. "Congruences." Ch. 3 in Elementary Number Theory. Berlin: Springer-Verlag, pp. 37-63, 1998.Nagell, T. "Theory of Congruences." Ch. 3 in Introduction to Number Theory. New York: Wiley, pp. 68-131, 1951.Séroul, R. "Congruences." §2.5 in Programming for Mathematicians. Berlin: Springer-Verlag, pp. 11-12, 2000.Shanks, D. Solved and Unsolved Problems in Number Theory, 4th ed. New York: Chelsea, p. 55, 1993.

Referenced on Wolfram|Alpha

Congruence

Cite this as:

Weisstein, Eric W. "Congruence." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Congruence.html

Subject classifications