we begin with a bit of algebra.
We have seen that in division with remainder of an integer a ∈ Z by a natural
number 0 < m ∈ N one has the unique representation
a = qm + r, 0 ≤ r < m.
Here r is called the remainder after division of a by m or the residue of a modulo
m, and it holds that m divides a − r without remainder, or in mathematical
notation,
m | (a − r).
This statement about divisibility was given a new notation by Gauss, in
analogy to the equal sign:1
a ≡ r mod m
say “a is congruent to r modulo m”).
Congruence modulo a natural number m is an equivalence relation on the
set of natural numbers. This means that the set R := { (a, b) | a ≡ b mod m }
of integer pairs satisfying m | (a − b) has the following properties, which result
immediately from division with remainder:
· R is reflexive: For all integers a it holds that (a, a) is an element of R, that is,
we have a ≡ a mod m.
· R is symmetric: If (a, b) is in R, then so is (b, a); that is, a ≡ b mod m
implies b ≡ a mod m.
· R is transitive: If (a, b) and (b, c) are in R, then so is (a, c); that is,
a ≡ b mod m and b ≡ c mod m implies a ≡ c mod m.
The equivalence relation R partitions the set of integers into disjoint sets, called
equivalence classes: Given a remainder r and a natural number m > 0 the set
r := { a | a ≡ r mod m },
or, in other notation, r + mZ, is called the residue class of r modulo m. This class
contains all integers that upon division by m yield the remainder r .
Here is an example: Let m = 7, r = 5; then the set of integers that upon
division by 7 yield the remainder 5 is
5 = 5 + 7 · Z = { . . . , −9, −2, 5, 12, 19, 26, 33, . . . }.
Two residue classes modulo a fixed number m are either the same or disjoint.2
Therefore, a residue class can be uniquely identified by any of its elements. Thus
the elements of a residue class are called representatives, and any element can
serve as representative of the class. Equality of residue classes is thus equivalent to
the congruence of their representatives with respect to the given modulus. Since
upon division with remainder the remainder is always smaller than the divisor,
for any integer m there can exist only finitely many residue classes modulo m.
Now we come to the reason for this extensive discussion: Residue classes
are objects with which one can do arithmetic, and in fact, by employing their
representatives. Calculating with residue classes has great significance for algebra
and number theory and thus for coding theory and modern cryptography. In what
follows we shall attempt to clarify the algebraic aspects of modular arithmetic.
Let a, b, and m be integers, m > 0. For residue classes a and b modulo m
we define the relations “+” and “·”, which we call addition and multiplication
(of residue classes), since they are based on the like-named operations on the
integers:
a + b := a + b (the sum of classes is equal to the class of the sum);
a · b := a · b ( product of classes is equal to the class of the produc)
