Mathematics for Computer Science

Chapter 8 Number Theory264

wherer 1 ;r 22 Œ0::n/. Subtracting the second equation from the first gives:

abD.q 1 q 2 /nC.r 1 r 2 /;

wherer 1 r 2 is in the interval.n;n/. Nowab .modn/if and only ifn
divides the left side of this equation. This is true if and only ifndivides the right
side, which holds if and only ifr 1 r 2 is a multiple ofn. But the only multiple of
nin.n;n/is 0, sor 1 r 2 must in fact equal 0, that is, whenr 1 WWDrem.a; n/D
r 2 WWDrem.b; n/. 

So we can also see that

29 15 .mod7/ because rem.29; 7/D 1 Drem.15; 7/:

Notice that even though “(mod 7)” appears on the end, thesymbol isn’t any more
strongly associated with the 15 than with the 29. It would probably be clearer to
write 29 mod 715 , for example, but the notation with the modulus at the end is
firmly entrenched, and we’ll just live with it.
The Remainder Lemma 8.6.1 explains why the congruence relation has proper-
ties like an equality relation. In particular, the following properties^7 follow imme-
diately:

Lemma 8.6.2.

aa .modn/ (reflexivity)

abIFFba .modn/ (symmetry)

.ab ANDbc/IMPLIESac .modn/ (transitivity)

We’ll make frequent use of another immediate corollary of the Remainder Lemma 8.6.1:

Corollary 8.6.3.
arem.a; n/ .modn/

Still another way to think about congruence modulonis that itdefines a partition
of the integers intonsets so that congruent numbers are all in the same set. For
example, suppose that we’re working modulo 3. Then we can partition the integers
into 3 sets as follows:

f :::; 6; 3; 0; 3; 6; 9; ::: g

f :::; 5; 2; 1; 4; 7; 10; ::: g

f :::; 4; 1; 2; 5; 8; 11; ::: g

(^7) Binary relations with these properties are calledequivalence relations, see Section 9.10.