Discrete Mathematical Structures by Pearson

7-16 Discrete Mathematical Structures

(5) Commutative Law: The operation is commutative as the corresponding rows and columns

are identical in the composition table. For example, 2 ×

5

3 = 1 = 3 ×

5

2.

Hence G is an abelian group.

7.4 CONGRUENCES

Definition 7.3 Two integers a and b are said to be congruent modulo a positive integer m if

a - b is divisible by m, that is, there exists an integer k such that a - b = km and is written as a ≡ b

(mod m). Congruences behave as equalities as can be seen from the following relations:

1. If a ≡ b (mod m), then

(i) a + x ≡ b + x (mod m)

(ii) ax ≡ bx (mod m)

2. If a ≡ b (mod m) and c ≡ d (mod m), then

(i) a + c ≡ b + d (mod m)

(ii) a - c ≡ b - d (mod m)

(iii) ac ≡ bd (mod m)

7.4.1 Residue Classes