Section 5.1 Relations
343
from the classes having the same denominator and add those representatives. Our
answer is the class to which the resulting sum belongs, and we usually name the
class by using a reduced fraction. Thus, to add 31∙2 4 + 33∙10 4, we represent 31∙24
by 5∙10 and 33∙10 4 by 3∙10. The sum of 5∙10 and 3∙10 is 8∙10, and 38∙10 4 is
customarily named 34∙5 4. This procedure is so familiar that it is generally written as 1∙2 + 3∙10 = 4∙5; nonetheless, equivalence classes of fractions are being
manipulated by means of representatives.
example 15
We will define a binary relation of congruence modulo 4 on the set Z of integers. An integer x is congruent modulo 4 to y, symbolized by x ≡ 4 y, or x ≡ y
(mod 4), if x − y is an integral multiple of 4. Congruence modulo 4 is an
equivalence relation on Z. To construct the equivalence classes, note that 304, for
example, will contain all integers differing from 0 by a multiple of 4, such as 4, 8,
−12, and so on. The distinct equivalence classes are
30 4 = 5…, −8, −4, 0, 4, 8, …6
31 4 = 5…, −7, −3, 1, 5, 9, …6
32 4 = 5…, −6, −2, 2, 6, 10, …6
33 4 = 5…, −5, −1, 3, 7, 11, …6
There is nothing special about the choice of 4 in Example 15; we can give a
definition for congruence modulo n for any positive integer n.
DefInItIon congRuence Modulo n
For integers x and y and positive integer n,
x ≡ y (mod n) if x − y is an integral multiple of n
This binary relation is an equivalence relation on Z for any positive integer n (see Exercise 46). This equivalence relation and the resulting equivalence
classes can be used for integer arithmetic on a computer. An integer is stored as
a sequence of bits (0s and 1s) within a single memory location. Each computer
allocates a fixed number of bits for a single memory location (this number varies
depending on the architecture of the computer—how its memory space is laid
out). The larger the integer, the more bits required to represent it. Therefore each
machine has some limit on the size of the integers it can store. Suppose that n − 1
is the maximum size and that x and y are integer values with 0 ≤ x ≤ n − 1,
0 ≤ y ≤ n − 1. If the sum x + y exceeds the maximum size, it cannot be stored.
As an alternative, the computer may perform addition modulo n and find the
remainder r when x + y is divided by n.
343
from the classes having the same denominator and add those representatives. Our
answer is the class to which the resulting sum belongs, and we usually name the
class by using a reduced fraction. Thus, to add 31∙2 4 + 33∙10 4, we represent 31∙24
by 5∙10 and 33∙10 4 by 3∙10. The sum of 5∙10 and 3∙10 is 8∙10, and 38∙10 4 is
customarily named 34∙5 4. This procedure is so familiar that it is generally written as 1∙2 + 3∙10 = 4∙5; nonetheless, equivalence classes of fractions are being
manipulated by means of representatives.
example 15
We will define a binary relation of congruence modulo 4 on the set Z of integers. An integer x is congruent modulo 4 to y, symbolized by x ≡ 4 y, or x ≡ y
(mod 4), if x − y is an integral multiple of 4. Congruence modulo 4 is an
equivalence relation on Z. To construct the equivalence classes, note that 304, for
example, will contain all integers differing from 0 by a multiple of 4, such as 4, 8,
−12, and so on. The distinct equivalence classes are
30 4 = 5…, −8, −4, 0, 4, 8, …6
31 4 = 5…, −7, −3, 1, 5, 9, …6
32 4 = 5…, −6, −2, 2, 6, 10, …6
33 4 = 5…, −5, −1, 3, 7, 11, …6
There is nothing special about the choice of 4 in Example 15; we can give a
definition for congruence modulo n for any positive integer n.
DefInItIon congRuence Modulo n
For integers x and y and positive integer n,
x ≡ y (mod n) if x − y is an integral multiple of n
This binary relation is an equivalence relation on Z for any positive integer n (see Exercise 46). This equivalence relation and the resulting equivalence
classes can be used for integer arithmetic on a computer. An integer is stored as
a sequence of bits (0s and 1s) within a single memory location. Each computer
allocates a fixed number of bits for a single memory location (this number varies
depending on the architecture of the computer—how its memory space is laid
out). The larger the integer, the more bits required to represent it. Therefore each
machine has some limit on the size of the integers it can store. Suppose that n − 1
is the maximum size and that x and y are integer values with 0 ≤ x ≤ n − 1,
0 ≤ y ≤ n − 1. If the sum x + y exceeds the maximum size, it cannot be stored.
As an alternative, the computer may perform addition modulo n and find the
remainder r when x + y is divided by n.