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. |

$[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.

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.

**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.