Congruence modulo m and its properties

Congruence modulo m is a way of saying that two integers have the same remainder when divided by m.

It is written as:

a ≡ b (mod m) and read as: "a is congruent to b modulo m."

This means: m ∣ (a−b) or m divides the difference between a and b.

Example 1:

17 ≡ 5 (mod 6)

Step 1. Divide both numbers by its modulo

       17 ÷ 6 = 2 remainder 5

       5 ÷ 6 = 0 remainder 5

Both numbers have the same remainder when divided by 6.

       therefore: 17 ≡ 5 (mod 6) is true. read as "17 is congruent to 5 modulo 6.“

Another way is to check whether the difference between the two numbers is divisible by it’s modulo m,

       17 − 5 = 12

Since: 12 ÷ 6 = 2

and 2 is an integer, 12 is divisible by 6.

       therefore: 17 ≡ 5 (mod 6) is true.

Example 2:

23 ≡ 5 (mod 6)

Step 1. Divide both numbers by its modulo

       23 ÷ 6 = 3 remainder 5

       5 ÷ 6 = 0 remainder 5

Both numbers have the same remainder when divided by 6.

       therefore: 23 ≡ 5 (mod 6) is true. read as “23 is congruent to 5 modulo 6.”

Another way is to check whether the difference between the two numbers is divisible by its modulo m,

       23 − 5 = 18

Since: 18 ÷ 6 = 3

and 3 is an integer, 18 is divisible by 6.

       therefore: 23 ≡ 5 (mod 6) is true.

Properties of Congruence Modulo m

1. Reflexive Property Every integer is congruent to itself.

a ≡ a (mod m)

Example:

8 ≡ 8 (mod 5)

8 ÷ 5 = 1 remainder 3

8 ÷ 5 = 1 remainder 3

Both numbers have the same remainder when divided by 5.

             therefore: 8 ≡ 8 (mod 5) is true.

2. Symmetric Property If one number is congruent to another, then the reverse is also true.

If: a ≡ b (mod m)

then: b ≡ a (mod m)

Example:

14 ≡ 2 (mod 6) 

2 ≡ 14 (mod 6)

14 ÷ 6 = 2 remainder 2

2 ÷ 6 = 0 remainder 2

Both numbers have the same remainder when divided by 6.

             therefore: 14 ≡ 2 (mod 6) is true.

2 ÷ 6 = 0 remainder 2

14 ÷ 6 = 2 remainder 2

Both numbers have the same remainder when divided by 6.

             therefore: 2 ≡ 14 (mod 6) is true.

3. Transitive Property If one number is congruent to a second number, and the second is congruent to a third number, then the first is congruent to the third.

If: a ≡ b (mod m)

and b ≡ c (mod m)

then: a ≡ c (mod m)

Example

20 ≡ 8 (mod 6)

8 ≡ 2 (mod 6)

therefore:

20 ≡ 2 (mod 6)  

20 ÷ 6 = 3 remainder 2

8 ÷ 6 = 1 remainder 2

Both numbers have the same remainder when divided by 6.

             therefore: 20 ≡ 8 (mod 6) is true.

8 ÷ 6 = 1 remainder 2

2 ÷ 6 = 0 remainder 2

Both numbers have the same remainder when divided by 6.

             therefore: 8 ≡ 2 (mod 6) is true.

20 ÷ 6 = 3 remainder 2

2 ÷ 6 = 0 remainder 2

Both numbers have the same remainder when divided by 6.

             therefore: 20 ≡ 2 (mod 6) is true.

4. Addition Property

If: a ≡ b (mod m)

and c ≡ d (mod m)

then: a + c ≡ b + d (mod m)

Example:

7 ≡ 2 (mod 5)

8 ≡ 3 (mod 5)

         7 + 8 ≡ 2 + 3 (mod 5)

         15 ≡ 5 (mod 5)

7 ÷ 5 = 1 remainder 2

2 ÷ 5 = 0 remainder 2

Both numbers have the same remainder when divided by 5.

             therefore: 7 ≡ 2 (mod 5) is true.

8 ÷ 5 = 1 remainder 3

3 ÷ 5 = 0 remainder 3

Both numbers have the same remainder when divided by 5.

             therefore: 8 ≡ 3 (mod 5) is true.

15 ÷ 5 = 3 remainder 0

5 ÷ 5 = 1 remainder 0

Both numbers have the same remainder when divided by 5.

             therefore: 15 ≡ 5 (mod 5) is true.

5. Subtraction Property

If: a ≡ b (mod m)

and c ≡ d (mod m)

then: a - c ≡ b - d (mod m)

Example:

17 ≡ 5 (mod 6)

14 ≡ 2 (mod 6)

         17 - 14 ≡ 5 - 2 (mod 6)

         3 ≡ 3 (mod 6)

17 ÷ 6 = 2 remainder 5

5 ÷ 6 = 0 remainder 5

Both numbers have the same remainder when divided by 5.

             therefore: 17 ≡ 5 (mod 6) is true.

14 ÷ 6 = 2 remainder 2

2 ÷ 6 = 0 remainder 2

Both numbers have the same remainder when divided by 5.

             therefore: 14 ≡ 2 (mod 6) is true.

3 ÷ 6 = 0 remainder 3

3 ÷ 6 = 0 remainder 3

Both numbers have the same remainder when divided by 5.

             therefore: 3 ≡ 3 (mod 6) is true.

6. Multiplication Property

If: a ≡ b (mod m)

and c ≡ d (mod m)

then: ac ≡ bd (mod m)

Example:

4 ≡ 1 (mod 3)

5 ≡ 2 (mod 3)

         (4)(5)≡ (1)(2) (mod 3)

         20 ≡ 2 (mod 3)

4 ÷ 3 = 1 remainder 1

1 ÷ 3 = 0 remainder 1

Both numbers have the same remainder when divided by 5.

             therefore: 4 ≡ 1 (mod 3) is true.

5 ÷ 3 = 1 remainder 2

2 ÷ 3 = 0 remainder 2

Both numbers have the same remainder when divided by 5.

             therefore: 2 ≡ 2 (mod 3) is true.

20 ÷ 3 = 6 remainder 2

2 ÷ 3 = 0 remainder 2

Both numbers have the same remainder when divided by 5.

             therefore: 20 ≡ 2 (mod 3) is true.