CHAP. 11] PROPERTIES OF THE INTEGERS 275
Remark:Supposemis positive, andais any integer. By the Division Algorithm, there exist integersqandr
with 0=r≤msuch thata=mq+r. Hence
mq=a−r or m|(a−r) or a≡r(modm)Accordingly:
(1) Any integerais congruent modulomto a unique integer in the set{ 0 , 1 , 2 ,...,m− 1 }The uniqueness comes from the fact thatmcannot divide the difference of two such integers.(2) Any two integersaandbare congruent modulomif and only if they have the same remainder when divided
bym.Residue Classes
Since congruence modulomis an equivalence relation, it partitions the setZof integers into disjoint equiv-
alence classes called theresidue classes modulom. By the above remarks, a residue class consists of all those
integers with the same remainder when divided bym. Therefore, there aremsuch residue classes and each
residue class contains exactly one of the integers in the set of possible remainders, that is,
{ 0 , 1 , 2 , ...,m− 1 }Generally speaking, a set ofmintegers{a 1 ,a 2 , ...,am}is said to be acomplete residue system modulo mif each
aicomes from a distinct residue class. (In such a case, eachaiis called arepresentativeof its equivalence class.)
Thus the integers from 0 tom−1 form a complete residue system. In fact, anymconsecutive integers form
a complete residue system modulom.
The notation[x]m, or simply [x] is used to denote the residue class (modulom) containing an integer x, that
is, those integers which are congruent tox. In other words,
[x]={a∈Z|a≡x(modm)}Accordingly, the residue classes can be denoted by
[ 0 ],[ 1 ],[ 2 ],...,[m− 1 ]or by using any other choice of integers in a complete residue system.
EXAMPLE 11.11 The residue classes modulom=6 follow:
[ 0 ]={...,− 18 ,− 12 ,− 6 , 0 , 6 , 12 , 18 ,...}, | 3 |={...,− 15 ,− 9 ,− 3 , 3 , 9 , 15 , 21 ,...}
[ 1 ]={...,− 17 ,− 11 ,− 5 , 1 , 7 , 13 , 19 ,...}, | 4 |={...,− 14 ,− 8 ,− 2 , 4 , 10 , 16 , 22 ,...}
[ 2 ]={...,− 16 ,− 10 ,− 4 , 2 , 8 , 14 , 20 ,...}, | 5 |={...,− 13 ,− 7 ,− 1 , 5 , 11 , 17 , 23 ,...}Notethat{− 2 ,− 1 , 0 , 1 , 2 , 3 }is also a complete residue system modulom=6, and these representatives have
minimal absolute values.
Congruence Arithmetic
The next theorem (proved in Problem 11.35) tells us that, under addition and multiplication, the congruence
relation behaves very much like the relation of equality. Namely:
Theorem11.22: Supposea≡c(modm) andb≡d(modm). Then:
(i)a+b≡c+d(modm); (ii)a·b≡c·d(modm)
Remark:Supposep(x)is a polynomial with integral coefficients. Ifs≡t(modm), then using Theorem 11.22
repeatedly we can show thatp(s)≡p(t)(modm).