Linear Diophantine Equations and Linear Congruences - Introduction to Cryptography with Java Applets - page 93

E XAMPLES .
a. 7 7 (mod 9) (Clearly, since 9|(7 7) = 0).
b. 8 2 (mod 6) and so 2 8 (mod 6) (Since 6|(8 2) = 6 iff 6|(2 8) = 6).
c. 7 3 (mod 5) and 3 2 (mod 5) implies 7 2 (mod 5).
Proposition 18 tells us that congruences modulo m partition the integers into m distinct
subsets modulo m , and each subset contains integers that are all congruent to each other
modulo m . For example, congruences modulo 3 partition the integers into 3 subsets:

a. {. . . , 9, 6, 3, 0, 3, 6, 9, . . .}

b. {. . . , 8, 5, 2, 1, 4, 7, 10, . . .}

c. 1, 2, 5, 8, 11, . . .}

All of the integers in set (a) are congruent to each other modulo 3. Likewise for sets (b)
and (c). (Verify.) Also, there are no integers that do not belong to exactly one of these sets.
Now, consider the subsets consisting of only the nonnegative members of sets (a), (b), and
(c). Note that no such subset is empty, and so each will have a minimal element. For the set
of nonnegative elements of set (a), this minimal element is 0. For set (b), the minimal pos-
itive element is 1, and 2 is the minimal positive element of set (c). These particular ele-
ments are often used as representatives of the congruence classes in which they reside, and
a definition for them follows.

{. . . , 7, 4,

Definition
Let b be an integer, and let m be a positive integer. All integers congruent to b modulo
m are called residues of b modulo m . The least nonnegative residue, or lnr, of b mod-
ulo m is the least nonnegative integer congruent to b modulo m .
Again, note that such a least nonnegative residue always exists, just by noting that
the least nonnegative residue r of c modulo m > 0 is the very same r obtained from the
division algorithm

c = dq + r 0

≤ r < d

which we already know always exists.

E XAMPLES .
a. The lnr of 29 modulo 13 is 3. That is, 3 29 (mod 13), and 3 is the smallest nonnega-

tive integer congruent to 29 modulo 13.

b. 2 (mod 6), and 2 is the smallest nonnegative number congruent to 44 modulo 6,

hence it is the lnr of 44 modulo 6.
c.

44

17 modulo 5.
Note that in all of the examples, the lnr is just r from the division algorithm, for
a.

17 2 3 (mod 5), and 3 is the lnr of

29 = 13 2 + 3,