If two numbers 
and 
have the property that their difference
is integrally divisible by a number
(i.e., 
is an integer), then 
and 
are said to be "congruent modulo 
." The number 
is called the modulus, and the
statement "
is congruent to 
(modulo 
)"
is written mathematically as
 |
(1)
|
If 
is not integrally divisible
by 
, then it is said that "
is not congruent to 
(modulo 
)," which is written
 |
(2)
|
The explicit "(mod 
)"
is sometimes omitted when the modulus 
is understood by context, so in such cases, care must be taken
not to confuse the symbol 
with the equivalence sign.
The quantity 
is sometimes called the "base," and the quantity 
is called the residue or remainder.
There are several types of residues. The common residue
defined to be nonnegative and smaller than 
, while the minimal residue
is 
or 
, whichever is smaller in absolute
value.
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 
.
If one starts at 40 minutes past the hour and then waits another 35 minutes, 
, so the current time
would be 15 minutes past the (next) hour.
Similarly, "hour arithmetic" on a 12-hour clock uses a modulus of 
, so 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 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 
and 
, then it follows that 
, but usually not that 
or 
. 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 
and 
, then important properties of congruences include
the following, where 
means "implies":
1. Equivalence: 
(which can be regarded as a definition).
2. Determination: either 
or 
.
3. Reflexivity: 
.
4. Symmetry: 
.
5. Transitivity: 
and 
.
6. 
.
7. 
.
8. 
.
9. 
.
10. 
.
11. 
and ![a=b (mod m_2)=>a=b (mod [m_1,m_2])](/images/equations/Congruence/Inline51.svg)
, where ![[m_1,m_2]](/images/equations/Congruence/Inline52.svg)
is the least common
multiple.
12. 
,
where 
is the greatest common divisor.
13. If 
,
then 
, for 
a polynomial.
Properties (6-8) can be proved simply by defining
 |  |  |
(3)
|
 |  |  |
(4)
|
where 
and 
are integers.
Then
 |  |  |
(5)
|
 |  |  |
(6)
|
 |  |  |
(7)
|
so the properties are true.
Congruences apply to fractions (i.e., rational numbers) as well as integers, and may be termed fractional congruences.
." In