Sales Toll Free No: 1-855-666-7446

Complete Residue System

Top
 Sub Topics Number theory has its applications in various fields of science and mathematics such as cryptography, product identification codes, etc. a mod b gives the remainder after a is divided by b. Congruence is one such important application of number system and modular arithmetic which is frequently used in real world. Let m be a natural number and a, b as integers. Then a is congruent to b modulo n if (a - b) is divisible by n. As an example we can see 28 is congruent to 3 modulo 5 which means (28 - 3) = 25 is divisible by 5. When any integer is divided by a natural number n, the remainder can be {0, 1, 2,.. , n-1}. Let us take the natural number 4. When any integer is divided my 4, then a mod 4 can be 0, 1, 2, 3. Thus, this modulo operation will divide the integer class in disjoint classes {[0], [1], [2], [3]}. The class [1] will represent all the integers that will remainder 1 after division with 4.

Definition

Suppose there is an integer a and a natural number n, then the congruence class of a modulo n will be denoted by $[a]_{n}$, which will give all the integers that are congruent to a modulo n. The equivalence classes defined by the congruence relation modulo m is known as residue class modulo m.

$[a]= {n\epsilon \mathbb{Z}: a = n\ mod\ m, m\ \epsilon\ \mathbb{N}}$

Suppose we have m = 3, and n = 0. The equivalence classes will be [0], [1], [2] as 0, 1, 2 are the only remainders obtained after division by 3.

[0] = {..., -3, 0, 3, 6, 9, ...}

[1] = {..., -1, 1, 4, 7, 10, ...}

[2] = {..., -2, 2, 5, 9, 11, ...}

Now, we put n = 2, and m = 3. The equivalence classes will still be [0], [1], [2] but they will be the remainder of (b - 2) divided by 3 where b is any integer.

[0] = {..., -4, -1, 2, 5, ...}

[1] = {..., -5, -2, 3, 6, ...}

[2] = {..., -6, -3, 0, 4,...}

A set of integers is called complete residue system when every integer is congruent to a unique member of the set of modulo m, which means that the set contains exactly one member of each equivalence class modulo m. A consecutive string of m integers will make a complete residue system for m.

As an example we can see that the set {2, 3, 4} contains one member from each equivalence class [0], [1], [2] defined by congruence relation modulo 3. A complete residue system is a bijection (one to one onto relation) between a set of elements and the different residue classes modulo m.

Properties

Given are the basic properties of congruence relation and residue classes:

1) Congruence is an equivalence relation, that is, for a relation between two integers a, b where a = b mod m is reflexive, symmetric and transitive.

2) The congruence relation on the natural number m will divide the set of integers into m equivalence classes which are disjoint sets, that is, no integer can be a part of more than one equivalence class for a natural number.

3) Congruence can be added. If a = b mod m, p = q mod m then (a + p) = (b + q) mod m.

4) Congruence can be multiplied. If a = b mod m, p = q mod m then (a * p) = (b * q) mod m.

5) If two integers a, b have same remainder when divided by m then a = b mod m.

6) If a = b mod m, then $a^{i}=b^{i}$ mod m.

7) If a = b mod m, then ka = kb mod m.

8) If a = b mod m, a = b mod n then a = b mod(lcm(m, n)).

9) If GCD(b, m) = 1, and the numbers $[a_{1},a_{2},...,a_{n}]$ form a complete residue system mod m then $(b\times a_{1})+c...(b\times a_{n})+c$ also forms a complete residue system.

Proof

Statement: Any set of m consecutive integers is a complete residue system modulo m.

Proof: Let us take an integer i. From the statement we have to prove that {i + 0, i + 1, ..., i + (m -1)} is a complete residue system modulo m. ... (1)

We have {0, 1, 2, ..., m - 1} as a complete residue system modulo m.

For any integer a there exists a $k\ \epsilon\ {0, 1, 2, ..., m + 1}$ such that,

a - i = k mod m

a = (i + k) mod m

Now, let us suppose $k_{1}, k_{2}\epsilon {0, 1, 2, ..., m + 1}$

We get,  a = $k_{1} + i$ mod m which implies a - i = $k_{1}$ mod m

Similarly a = $k_{2} + i$ mod m which implies a - i = $k_{2}$ mod m

Hence, (a - i) is found to be congruent to two different elements of the complete residue system {0, 1, ..., m - 1} which is a contradiction. Hence, each (k + i) is a distinct element which corresponds to different congruent classes modulo m.

This proves that {i + 0, i + 1,.. i + m - 1} to be a complete residue system modulo m.