6.7 Congruences 1056.7 Congruences...........................
Notation is not part of the bare logical structure of mathematics: we could
denote the set of real numbers byV, or addition by #, and the meaning
of mathematical results would be the same. But a good notation may be
wonderfully suggestive, leading to a real conceptual breakthrough. One
such important step was taken when Carl Friedrich Gauss noticed that
we use the phrase “agives the same remainder asbwhen divided bym”
very often, and that this relation behaves quite similarly to equality. He
introduced a notation for this, calledcongruence.
FIGURE 6.4. Carl Friedrich Gauss (1777–1855).Ifaandbgive the same remainder when divided bym(wherea, b, mare
integers andm>0), then we write
a≡b (modm)(read:ais congruent tobmodulom). An equivalent way of saying this is
thatmis a divisor ofb−a. The numbermis called themodulusof the
congruence relation.
This notation suggests that we want to consider this relation as an ana-
logue of equality. And indeed, many of the properties of equality are valid
for congruences, at least if we keep the modulusmfixed. We havereflexiv-
ity,
a≡a (modm),
symmetry,
a≡b (modm)=⇒ b≡a (modm),