| 释义 |
CongruenceIf  is integrally divisible by  , then  and  are said to be congruent with Modulus . This is written mathematically as  (mod ). If is not divisible by , then wesay  (mod ). The (mod ) is sometimes omitted when the Modulus isunderstood for a given computation, so care must be taken not to confuse the symbol  with that for anEquivalence. The quantity is called the Residue orRemainder. The Common Residue is taken to be Nonnegative and smaller than  , and the MinimalResidue is or  , whichever is smaller in Absolute Value. In many computer languages (such as FORTRAN orMathematica ), the Common Residue of (mod ) is written mod(c,a).
Congruence arithmetic is perhaps most familiar as a generalization of the arithmetic of the clock: 40 minutes past the hourplus 35 minutes gives  , or 15 minutes past the hour, and 10 o'clock a.m. plus five hours gives , or 3 o'clock p.m. Congruences satisfy a number of important properties, and are extremely useful inmany areas of Number Theory. Using congruences, simple Divisibility Tests to check whether a given number isdivisible 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  and  , then it follows that  , but usually not that  or  . In addition, by ``rolling over,'' congruences discardabsolute information. For example, knowing the number of minutes past the hour is useful, but knowing the hour the minutesare past is often more useful still.
Let  and  , then important properties of congruences include the following, where  means``Implies'': - 1. Equivalence:
 . - 2. Determination: either
 or  . - 3. Reflexivity:
 . - 4. Symmetry:
 . - 5. Transitivity: and
 . - 6.
 . - 7.
 . - 8.
 . - 9.
 . - 10.
 . - 11.
 and  , where  is theLeast Common Multiple. - 12.
 , where  is the Greatest CommonDivisor. - 13. If , then
 , for  a Polynomial.
Properties (6-8) can be proved simply by defining
where  and  are Integers. Then
so the properties are true.
Congruences also apply to Fractions. For example, note that
 | (6) |
 | (7) |
 mod , use an Algorithm similar to the Greedy Algorithm. Let  and find
 | (8) |
 is the Ceiling Function, then compute
 | (9) |
 , then
 | (10) |
A Linear Congruence
 | (11) |
 | (12) |
 is the Greatest Common Divisor, in which case the solutions are  ,  , , ...,  , where  . If  , then there is only one solution.
A general Quadratic Congruence
 | (13) |
 | (14) |
 | (15) |
Two simultaneous congruences
 | (16) |
 | (17) |
 , and the single solution is
 | (18) |
References
Conway, J. H. and Guy, R. K. ``Arithmetic Modulo  .'' 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.
|
