Number theory 3

CONGRUENCE RELATION
Let m be a positive integer. We say that a is congruent to b modulo m. written
a ? b (modulo m) or simply a ? b (mod m)
if m divides the difference a ?b . The integer m is called the modulus. The negation of a ? b (mod m) is written
a ? b (mod m). For example:
(i) 87 ? 23 (mod 4) since 4 divides 87 ? 23 = 64.
(ii) 67 ? 1 (mod 6) since 6 divides 67 ? 1 = 66.
(iii) 72 ? ?5 (mod 7) since 7 divides 72 ? (?5) = 77.
(iv) 27 ? 8 (mod 9) since 9 does not divide 27 ? 8 = 19.
Our first theorem (proved in Problem 11.34) states that congruence modulo m is an equivalence relation.
Theorem 11.21: Let m be a positive integer. Then:
(i) For any integer a, we have a ? a (mod m).
(ii) If a ? b (mod m), then b ? a (mod m).
(iii) If a ? b (mod m) and b ? c (mod m), then a ? c (mod m).
CHAP. 11] PROPERTIES OF THE INTEGERS 275
Remark: Suppose m is positive, and a is any integer. By the Division Algorithm, there exist integers q and r
with 0 = r ? m such that a = mq + r. Hence
mq = a ? r or m| (a ? r) or a ? r (mod m)
Accordingly:
(1) Any integer a is congruent modulo m to a unique integer in the set
{0, 1, 2, . . . , m ? 1}
The uniqueness comes from the fact that m cannot divide the difference of two such integers.
(2) Any two integers a and b are congruent modulo m if and only if they have the same remainder when divided
by m.
Residue Classes
Since congruence modulo m is an equivalence relation, it partitions the set Z of integers into disjoint equivalence
classes called the residue classes modulo m. By the above remarks, a residue class consists of all those
integers with the same remainder when divided by m. Therefore, there are m such 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 {a1, a2, . . . , am
} is said to be a complete residue system modulo m if each
ai comes from a distinct residue class. (In such a case, each ai is called a representative of its equivalence class.)
Thus the integers from 0 to m?1 form a complete residue system. In fact, any m consecutive integers form
a complete residue system modulo m.
The notation [x]
m, or simply [x] is used to denote the residue class (modulo m) containing an integer x, that
is, those integers which are congruent to x. In other words,
[x] = {a ? Z | a ? x (mod m)}
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 modulo m = 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, . . .}
Note that {?2,?1, 0, 1, 2, 3} is also a complete residue system modulo m = 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:
Theorem 11.22: Suppose a ? c (mod m) and b ? d (mod m). Then:
(i) a+ b ? c + d(mod m); (ii) a· b ? c · d(mod m)
Remark: Suppose p(x) is a polynomial with integral coefficients. If s ? t (mod m), then using Theorem 11.22
repeatedly we can show that p(s) ? p(t) (mod m).
276 PROPERTIES OF THE INTEGERS [CHAP. 11
EXAMPLE 11.12 Observe that 2 ? 8 (mod 6) and 5 ? 41 (mod 6). Then:
(a) 2 + 5 ? 8 + 41 (mod 6) or 7 ? 49 (mod 6)
(b) 2 · 5 ? 8 · 41 (mod 6) or 10 ? 328 (mod 6)
(c) Suppose p(x) = 3x2 ? 7x + 5. Then
p(2) = 12 ? 14 + 5 = 3 and p(8) = 192 ? 56 + 5 = 141
Hence 3 ? 141 (mod 6).
Arithmetic of Residue Classes
Addition and multiplication are defined for our residue classes modulo m as follows:
[a] + [b] = [a + b] and [a] · [b] = [ab]
For example, consider the residue classes modulo m = 6; that is,
[0], [1], [2], [3], [4], [5]
Then
[2] + [3] = [5], [4] + [5] = [9] = [3], [2]·[2] = [4], [2]·[5] = [10] = [4]
The content of Theorem 11.22 tells us that the above definitions are well defined, that is, the sum and product of
the residue classes do not depend on the choice of representative of the residue class.
There are only a finite number m of residue classes modulo m. Thus one can easily write down explicitly
their addition and multiplication tables when m is small. Figure 11-4 shows the addition and multiplication tables
for the residue classes modulo m = 6. For notational convenience, we have omitted brackets and simply denoted
the residue classes by the numbers 0, 1, 2, 3, 4, 5.
Fig. 11-4
Integers Modulo m, Zm
The integers modulo m, denoted by Zm, refers to the set
Zm = {0, 1, 2, 3, . . . , m ? 1}
where addition and multiplication are defined by the arithmetic modulo m or, in other words, the corresponding
operations for the residue classes. For example, Fig. 11-4 may also be viewed as the addition and multiplication
tables for Z6, This means:
There is no essential difference between Zm and the arithmetic of the residue
classes modulo m, and so they will be used interchangeably.
CHAP. 11] PROPERTIES