Some of equivalence relations have an additional property: operations on equivalent arguments lead to equivalent results.  We say in that case that an equivalence relation is a congruence. We shall develop this subject in the lecture 10 in more detail where we will concentrate on the abstract algebras. Now we will consider a particular case of congruences defined in the set of integer numbers Z.

Example 4.5.1
12 ≡5 (mod 7), 33 ≡ 23 (mod 5), 1024 ≡128 (mod 2), 82 ≡28 (mod 9), (-87) ≡ (+6) (mod 3).

It is easy to verify that for every x ,y ∈ Z,

Indeed, zero is divisible by any integer number p, so x ≡ x (mod p). If p|(x-y) then x-y = k*p for some k, hence y-x = -k*p and therefore p|(y-x). If x-y = kp and y-z = k'p then (adding up) we have x-z = (k+k')p, which means x ≡ z (mod p). Thus, the congruence modulo p is reflexive, symmetric and transitive relation, i.e. we have proved the following lemma:  

Let  p  be a natural number greater than 0 and let x mod p denote the remainder, and x div p denote the quotient of division of x by p. By definition, x div p is the greatest integer number which is less or equal to  x/p, i.e. x div p = ⎣ x/p ⎦, and the remainder of division by p is a natural number less than p. Hence, mod and div are two-argument operations:

In the set Z of all integer numbers, they satisfy the following condition:

We have  (-5) div 3 = -2 and (-5) mod 3 = 1, since 3*(-2) +1 = -5. Obviously, if  x mod p = 0 then x is divisible by p, i.e. p|x  or x = k*p for some integer number k.

Question 4.5.1 Find the quotient and the remainder of the division of  -21  by 9.

It is worthwhile to note that the remainder and the quotient of the division of a negative integer x can be easily calculated if we know the quotient and the remainder of -x, since for every x<0 and every natural number p, p>1 we have

Remark. On the left-hand side of the above eqivalence "(mod p)" is a part of the denotation of congruence relation  and on the right-hand side "mod p" is the operation "modulo p".

Proof of Lemma 4.5.2.
 
Let  x div p = k, x mod p = r. By the formula  (*) we obtain x  = kp + r. If x is congruent to y  modulo p, then by the definition, p|(x-y). Hence  x-y = k'p for some k' and therefore y = x - k'p = kp + r - k'p = (k-k')p + r. The last equality means that r = y mod p. Conversely, let x = kp + r and y = k'p + r' where r and r' are natural numbers less than p. If  (x mod p) = (y mod p), then r = r', and, therefore, x - y = kp - k'p = (k-k')p that is p|(x-y).

From lemma 4.5.2 immediately follows that congruence modulo p determines p classes of equivalence:

as every integer number divided by p gives exactly one of possible remainders: 0, 1,..., (p-1). The class [0] is the set of all integer numbers that are divisible by p, the class [1] is the set of all integer numbers that gives remainder 1 when divided by p, the class [2] is the set of all integer numbers that gives remainder 2 when divided by p etc. All the classes are infinite. The set of all equivalence classes with respect to congruence modulo p is denoted by [Z]_p.

Question 4.5.2 Consider the congruence modulo 7, and let x be in the class [4] and y in the class [5]. To which class does their sum (x+y) belong?

Let us remark, that if x = pk+i and y = pk'+j (i.e. x mod p = i and y mod p = j) then their sum is p*(k+k') + (i+j). Hence

Analogously, for mutiplication:  x * y = (pk+i)*(pk'+j) = p(pkk' + kj + k'i) + i*j. Thus

We conclude that addition and multiplication of congruent arguments lead to congruent results. 

Lemma 4.5.2 suggests that one can define operations on abstraction classes determined by a congruence in such a way that they  correspond to the usual arithmetic operations. Indeed, putting for all integer numbers x, y,

we define a couple of two-argument operations  ⊕ , ⊗ in the set [Z]_p. For the case when p = 3 we have:

It can be easily seen that the operations  ⊕, ⊗ satisfy properties similar to the properties of addition and multiplication in the set Z, for example both operations are commutative and associative. Verification of this fact is left to the Reader as an exercise.

Lemma 4.5.2 can be extended to the following: for arbitrary polynomial P in Z,

Question 4.5.3  Let us consider the set Z₆. Which of the following are valid?

« previous section

next section »