Congruence in Integers

Congruence relation in Z

Classifying non-negative integers

Z₀⁺ = {0, 1, 2, 3, 4, …} is the set of  non-negative integers. The '...' syimbol means that all the non-negative integers are included in that list. In the set Z₀⁺ can be done classifications like the following:

In this case Z₀⁺ has been classified in three subsets with an infinity of elements in each of them:

  {0, 3, 6, 9, …}, {1, 4, 7, 10, …}, {2, 5, 8, 11, …}.

Each one of these subsets can be identify by means of any of their elements. For instance using the smallest one. In this way, there is not ambiguity in saying "the class of 0", "the class of 1", the class of 2".

Also a special symbol can be adopted : 0* = {0, 3, 6, 9, …}, 1* = {1, 4, 7, 10, …}, 2* = {2, 5, 8, …}.

Every non-negative integer is in exactly one of these classes. For instance, 3472 is in one of them, though it is not evident where. It is convenient to have a fast method to determine the right class without writing down the complete list.

It can be observed that 0* is the class of non-negative integers of  the form 3k, where k takes all the values in {0, 1, 2, 3, ...}, that is in  Z₀⁺.

In the same way, 1* is the class of non-negative integers of  the form 3k + 1, where k takes all the values in {0, 1, 2, 3, ...}, that is in  Z₀⁺.

Also in the same way, 2* is the class of non-negative integers of  the form 3k + 2, where k takes all the values in {0, 1, 2, 3, ...} that is in  Z₀⁺.

The above description sugest a certain flavor of division of a number by 3. More precisely, with possible reminders of a division by 3. They might be 0, 1 or 2.

Effectively, in dividing by 3 any number of the class 0* the remainder is 0. In dividing by 3 any number of the class 1* the remainder is 1. In dividing by 3 any number of the class 2* the remainder is 2.

For 3472, it can be seen, by making the division by 3, that  3472 =  (3 × 1157) + 1. As the remainder is 1, it means that 3472 belongs to 1*.

As any element of a class can be accepted as representative, for instance 1* and 4* are the same class in this partition.

In above example,   Z₀⁺ has been partitioned in three classes. But the partition can be done in any number of classes.

Partition in four classes gives:

 0* = {0, 4, 8, 12, …}, 1* = {1, 5, 9, 13, …}, 2* = {2, 6, 10, 14, …}, 3* = {3, 7, 11, 15, …}.

In this partition, 3472 is in the class 0* since 3472 = (4 × 868) + 0.

Partitions in Z

The partition given in the first example can be extended to include negative integers:

                                         

the classes obtained are:

0* = {…, -9, -6, -3, 0, 3, 6, 9, …}; 
1* = {…, -8, -5, -2, 1, 4, 7, 10, …}; 
2* = {…, -7, -4, -1, 2, 5, 8, 11, …}. 

Note: "iff" means "if and only if"

The criterion by which it is decided if two numbers belong to the same class is the same as before. Two numbers belong to the same class, iff the difference between them is a multiple of 3. Alternatively, two numbers are in the same class, iff the remainder in dividing by 3 is the same.

Example: to determine in which class is -3805, divide it by 3:

As  -3805 = (-1268 × 3) – 1, the reminder -1 means that -3805 is in the class 2*

Also it can be seen that the difference between this number and any other in the same class is a multiple of 3. For instance,  8 – (-3805) = 3813 = 3 × 1271.

The classification of Z in four classes gives:

0* = {…, -12, -8, -4, 0, 4, 8, 12,…}
1* = {…, -11, -7, -3, 1, 5, 9, …}
2* = {…, -10, -6, -2, 2, 6, 10, …}
3* = {…, -9, -5, -1, 3, 7, 11, …}

In this partition, -3805 is in the class 3* because the remainder of the division by 4 is -1.
-3805 = (-951 × 4) – 1. Also, 3 – (-3805) = 3808, which is a multiple of 4.

Congruence modulo m

Above examples lead to a  generalization about numeric congruence.
If m is an integer grater than 1, the set of integers can be classified in m classes.
Two integers, a, b are in the same class, iff  a - b is a multiple of m.

A binary relation is defined in Z called congruence, modulo m. The following definition was formulated by Gauss:

a is congruent with b (mod m), iff , a – b is a multiple of m.

Note. To express that a is congruent with b it will be written a ≡ b

Above definition is equivalent to the already mentioned division criterion:

Dividing a by m gives r = a - k.m

Dividing b by m gives s =  b - t.m

If r = s then a - k.m = b - t.m. That is, a - b = (k - t).m. Conclusion: a ≡ b (mod m)

Conversely, if a ≡ b (mod m) then a - b  = u.m, for some integer u.

Dividing a by m gives a = s.m + f

Dividing b by m gives b =  t.m + g

Then  a - b = (s - t).m + f - g

As a ≡ b (mod m), a - b has to be multiple of m. Then, f - g = 0. that is f = g: the reminders in each division are equal.

Congruence in Z as an equivalence relation

A relation R defined in a set is an equivalence relation iff  R is reflexive, symetric and transitive.

The congruence relation is reflexive. In fact, a ≡ a (mod m) because a - a = 0 is multiple of m. Indeed, 0 is multiple of any integer z as 0 = 0 × z.

The congruence relation is symmetric: if a ≡ b (mod m) then b ≡ a (mod m). In fact, if a - b is multiple of m then b - a is also multiple of m.

The congruence relation is transitive. If a ≡ b (mod m) and b ≡ c (mod m) then a ≡ c (mod m).

Let's justify above assumption. The premises mean that a - b = t.m and a - c = u.m, for some integers t, u. By addition it is obtained, 
a - b + b - c = t.m + u.m. That is, a - c = (t + u).m. This means, a - c is multiple of m.

Partition induced by congruence in Z

In general, an equivalence relation R defined in a set determine a partition in it. This means that the set can be classified in non empty disjoint sets. The union of such sets gives the original set.

The classes induced by congruence  modulo m in Z can be designated by 0*, 1*, 2*, …, (m -1)*.
m* is the same as 0* since that clas contains all the multiples of m.

For any integer n chosen, n belongs to one and only one class of above list.

Proof.: In above list there are m classes. Suppose that  n belongs to a* and n belongs to b*, with a* different from b*. Then n ≡ a (mod m) and  n ≡ b (mod m). This implies that a ≡ b (mod m). That is, a* = b*, which contradicts previous assumption.

Other properties of congruence relation are the following:

 If a ≡ b (mod m) and c ≡ d (mod m) then (a + c) ≡ (b + d) (mod m)

Proof: a - b = k.m, for some integer k and c - d = tm, for some integer t.

Then a - b + c - d  = (k + t)m. 

This can be rewritten as (a + c) - (b + d) = (k + t)m

Conclusion: (a + c ) - (b + d) is multiple of m. That is, (a + c) ≡ (b + d) (mod m)

Example: From 9 ≡ -7 (mod 4) and 6 ≡ 10 (mod 4) it follows that  15 ≡ 3 (mod 4)

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

Proof: a - b = h.m, for some integer h and c - d = sm, for some integer s.

Then a = b + h.m and c = d + s.m

a.c = b.d + b.s.m + d.h.m + h.s.m.m

a.c - b.d = (b.s + d.h  + h.s.m).m

Conclusion: a.c - b.d is multiple of m. That is, a.c ≡ b.d  (mod m)

Example: From 9 ≡ -7 (mod 4) and 6 ≡ 10 (mod 4) it follows that 54 ≡ -70 (mod 4)

If a ≡ b (mod m)  then  a.c ≡ b.c (mod m)

This is a corollary of above property:

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

Example:  From 12 ≡ 25 (mod 13) it follows that 48 ≡ 100 (mod 13)

Using induction (see Peano) it can be shown the following:

If a ≡ b (mod m) then for any positive integer n, aⁿ ≡  bⁿ (mod m).

Proof: For n = 1 the statement is true. 
If the statement is true for n = k (induction hypothesis) it has to be proved for n = k + 1.

If a ≡ b (mod m) then for a positive integer k, a^k ≡  b^k (mod m). 
Then a.a^k ≡  b.b^k (mod m). That is a^k+1 ≡  b^k+1 (mod m).


Example: if  9 ≡ -7 (mod 4)  then  9³≡ (-7)³ (mod 4). that is, 729 ≡ -343  (mod 4)

Sums and products  modulo m

In what follows, tables for addition and multiplication for integers modulo 3 and modulo 4 are presented.

To obtain, for instance 3* + 2* (mod 4) it will be chosen  representatives of class 3*  and class 2* and perform ther ordinary sum betweem them. The result will be placed in its corresponding class. For instance, 3* + 2* = (3 + 2)* = 5* = 1* .
In analogous way, for the product. Example: 3* × 2* = (3 × 2)* = 6* = 2*

Addition table (mod 3)

+	0*	1*	2*
0*	0*	1*	2*
1*	1*	2*	0*
2*	2*	0*	1*

In {0*, 1*, 2*} this is a binary operation. 0* is the  neutral element. Each element has its opposite. For instance, the opposiye of 2* is 1*. Associative and commutative laws hold. Briefly, {0*, 1*, 2*} is a commutative group with respect to addition.


Multiplication table (mod 3)

×	0*	1*	2*
0*	0*	0*	0*
1*	0*	1*	2*
2*	0*	2*	1*

In {0*, 1*, 2*} this is a binary operation too. 0* has not inverse, 1* and 2* are inverses of themselves. 0* is absorbent. Associative and commutative laws hold too. Briefly, {0*, 1*, 2*} is a commutative group with respect to multiplication.

Distributive law holds. For instance, 2* × (1* + 2*) = 2* × 0* = 0* and (2* × 1*) + (2* × 2*) = 2* + 1* = 0*. Then  2* × (1* + 2*) = (2* × 1*) + (2* × 2*).

Addition and multiplication tables (mod 4)

{0*, 1*, 2*, 3*} is is a commutative group with respect to addition, as can be verified. In particular, the opposite of 3* is 1*; the opposite of 2* is 2*.

The multiplication is a binary operation in {0*, 1*, 2*, 3*}. 0* is absorbent. 1* is neutral. 2* has not inverse . Then, {0*, 1*, 2*, 3*} is not a group with respect to multiplication.

An anomalous situation like that in multiplication modulo 4 can be seen better in the following table for multiplication modulo 12.

×

0*

1*

2*

3*

4*

5*

6*

7*

8*

9*

10*

11*

0*

0*

0*

0*

0*

0*

0*

0*

0*

0*

0*

0*

0*

1*

0*

1*

2*

3*

4*

5*

6*

7*

8*

9*

10*

11*

2*

0*

2*

4*

6*

8*

10*

0*

2*

4*

6*

8*

10*

3*

0*

3*

6*

9*

0*

3*

6*

9*

0*

3*

6*

9*

4*

0*

4*

8*

0*

4*

8*

0*

4*

8*

0*

4*

8*

5*

0*

5*

10*

3*

8*

1*

6*

11*

4*

9*

2*

7*

6*

0*

6*

0*

6*

0*

6*

0*

6*

0*

6*

0*

6*

7*

0*

7*

2*

9*

4*

11*

6*

1*

8*

3*

10*

5*

8*

0*

8*

4*

0*

8*

4*

0*

8*

4*

0*

8*

4*

9*

0*

9*

6*

3*

0*

9*

6*

3*

0*

9*

6*

3*

10*

0*

10*

8*

6*

4*

2*

0*

10*

80*

6*

4*

2*

11*

0*

11*

10*

9*

8*

7*

6*

5*

4*

3*

2*

1*

Anomalous situations are for instance in  4* × 3* = 0* in which none of the factors is absorbent. Also in 6* × 3* = 6* where 3* is not the additive identical.

Generalization

In multiplication tables modulo 4 and modulo 12 are detected anomalous situations that seem to be linked with the factors of the considered modulo.

If the modulo is m (m ≥ 1) and the classes of the partition are 0*, 1*, …, (m – 1)*, it can be observed hat if h is a factor of m then there is an integer k such that h × k = m. As m* = 0*, h* ×  k* = 0*, where it is not necessary that at least one of the factors be equal to 0*.

If m is a prime number, its factors are, 1, m -1, -m. As m* = 0*, h* ×  k* = 0* , where none of the factors is 0*. In the equation h × k = m,  the possible values for  h, k are given in the following table:

h	k
1	m
m	1
-1	-m
-m	-1

If m is a prime number, h* ×  k* = 0* only if  any one of the factors h*, k*  is 0*; that is, if any of the factors h, k is 0 or m or -m.

Addition and multiplication tables modulo 7

In the following example, m = 7. The tables for addition and multiplication exhibit the properties which characterize a group.

Also, the in the set {0*, 1*, 2*, 3*, 4*, 5*, 6*} can be solved equations of the form a + x = b, ax = d, ax + d = f and systems of linear equations.

Using results of these tables, there can be solved equations like the following:

3* + x = 1*. It must to add the opposite of 3* to each side: 4* + (3* + x) = 4* + 1*. Use associative law to obtain 0* + x = 5*. Finally, x = 5*.

4*x = 5*. Multiply in both sides by the multiplicative inverse of 4*, which is 2*:
2*(4*x) = (2*)(5*); use associative law: (2*.4*).x = (2*)(5*); 1*x = 3*: x = 3*

3*x + 2* = 4*
(3*x + 2*) + 5* = 4* + 5*
3*x + (2* + 5*) = 2*
3*x = 2*
5*.(3*.x) = 5*.2*
(5*.3*).x = 3*
x = 3*

For the system of equations

3*x + 2*y = 1*

5*x + 4*y = 2*

Examine the determinant: (3*)(4*) – (5*)(2*) = 5* - 3* = 5* + 4* = 2*
The solution is:x = 0*, y = 4*/2* = (4*)(4*) = 2*.

For the system of equations

3*x + 2*y – 5*z = 4*

6*x - 4*y + 1*z = 2*

5*x + 3*y + 0*z = 1*

Kramer´s rule can be used as before.
In calculating determinants without the reduction modulo 7, it is obtained: det. = -189; det_x = -60; det_y = 37; det_z = 130.
The correspondent values modulo 7 are: det. = 0*; det_x = 3*; det_y = 2*; det_z = 4*.

As det. = 0* this system has not solution.

For the system of equations

3*x + 2*y – 5*z = 4*

6*x - 4*y + 1*z = 2*

5*x + 3*y - 6*z = 1*

det. = -45; det_x = 60; det_y = 145; det_z = 130, That is,  det. = 4*; det_x = 4*; det_y = 5*; det_z = 4*. 
From this it follows that 
x = 4*/4*; y = 5*/4*; z = 4*/4*. As the multiplicative inverse of 4* is 2*, 
x =(4*)(2*) = 1*; y = (5*)(2*) = 3*; z = (4*)(2*) = 1*.