2.1.3 Congruences

2.1.3 Congruences

Let n be a positive integer.

Definition 2.1.8 If a and b are integers, then a is said to be congruence to b modulo n,

written a ≡ b (mod n), if n devides (a - b). The integer n is called the modulus of the

congruence.

Theorem 2.1.10 (properties of congruences) For all a, a1,b,b1,c Є Z, the following are

true.

1. a ≡ b (mod n) if and only if a and b leave the same remainder when divided by n.

2. (reflexivity) a≡ a (mod n).

3. (symetry) If a ≡ b (mod n), then b ≡ a (mod n).

4. (transitivity) Ifa ≡ b (mod n), and b ≡ c (mod n), then a ≡ c (mod n).

5. If a ≡ a1 (mod n), and b ≡ b1 (mod n), then a + b ≡ a1 + b1 (mod n) and

ab ≡ a1b1 (mod n).

Definition 2.1.9 The integers modulo n, denoted Zn, is the set of (equivalence classes

of integers) {0, 1, 2,... ,n- 1}. Addition, subtraction, and multiplication in Zn are per-

formed modulo n.

Example 2.1.6 Z25 = {0, 1, 2,... ,24}.In Z25, 13 + 16 = 4, since 13 + 16 = 29=4(mod 25). Similarly, 13 · 16 = 8 in Z25.