We learnt in plane geometry that the term congruent means exactly same when superimposed on each other.

So, what could the statement $\unicode{0x201C}$Integer A is congruent to integer B$\unicode{0x201D}$ possibly mean? Let's find out.

When an integer, $a$, is divided by another integer $N$, then the remainder will always be an integer between  and .

The modulo operator is defined as integer division, where we discard the quotient and consider only the remainder. This remainder is called the the least residue of $a$ modulo $N$. Thus, all integers on the number line will have a least residue of $0$ to $N-1$ modulo $N$.

Let us say, two distinct integers $a$ and $b$ leave the same remainder $r$ when divided by $N$. Then we say that $a$, $b$ and $r$ are congruent to each other modulo $N$, and using mathematical the symbol $\equiv$, we write this as $a \equiv b \equiv r\ (mod\ N)$.

For example, the numbers $14$ and $20$, each leave a remainder of $2$ when divided by $6$. Therefore, we can write:

$14 \equiv 20 \equiv 2\ (mod\ 6)$ 

The following widget shows how each number on the number line maps to its residue, modulo a selected divisor. When you select any divisor $N$, the number circle is divided into $N$ equal parts with dots marked between $0$ to $N-1$ on the inside of the circle. As you rotate the circle the number line wraps or unwraps from around the circle. You can see that each number on the number line maps to a specific number inside the circle. This number on the inside shows you the remainder of the number outside, modulo the chosen divisor. The number circle formed in the widget, is also called the additive group modulo N.

Select a divisor of your choice between $2$ and $16$ in the widget below and trying rotating the circle.

The group formed by the numbers from $0$ to $N-1$ is called the additive group module $N$ because of two reasons:

- The group is closed under addition modulo $N$. That is when any two numbers from this group are added, and the remainder modulo $N$ is computed the result always maps to an element in this group.

- The group contains the element $0$ which is the additive identity element, that is when this number is added to any other number, it does not change the identity of that element.

Now we will take a brief look at multiplicative groups modulo $N$ and a few of their properties. If we consider any integer $N$, the integers between $1$ and $N-1$ that are co-prime to $N$ form the multiplicative group.

Note that the element $0$ does not form part of the multiplicative group. The most important properties of this multiplicative group are:

- These groups are closed under multiplication. They are $NOT$ closed under addition.

- Every element of this group is invertible modulo $N$, that is, for every element $a$ of the group, there exists an element $b$ such that $a \times b \equiv 1\ (mod\ N)$. That is when $a$ and $b$ are multiplied and the remainder modulo $N$ is taken, we get $1$.

- Zero is not a member of this group, because $0$ does not have a multiplicative inverse.

For example, the multiplicative group modulo $15$ is:
$\{1, 2, 4, 7, 8, 11, 13, 14\}$

You can see that the numbers $3, 5, 6, 9, 10, 12$ are not co-prime to $15$, and are therefore, not part of the multiplicative group.

As we saw in the previous widget, like positive integers, negative integers can also be mapped to a corresponding residue modulo a given integer.

If we choose $7$ as the divisor, then the number $-1$ can be written as:

$-1 = -1 \times 7 + 6$. Therefore, we can write that $-1 \equiv 6\ (mod\ 7)$.

Similarly,

$-11 = -2 \times 7 + 3$, therefore, $11 \equiv 3\ (mod\ 7)$

Notice that we can also write $-11$ as $-11 = -1 \times 7 + (-4)$.

But when we are referring to least residue, we always take the smallest positive integer as the least residue.

Therefore,

$-11 \equiv -4 \equiv 3\ (mod\ 7)$, is true, but

the least residue of $-11$ modulo $7$ is always $3$

Like normal integers, residues of numbers, exhibit a huge number of properties. We will take a look at some of the very important ones in this section.

An important property of congruence is as follows:

If $a \texttip{\equiv}{congruent to} b \pmod{N}$, then $a - b$ is divisible by $N$ or we can write $N | a-b$.

(In maths, the $|$ symbol is used to say divides. So, $3 | 12$ means $3$ divides $12$, and the symbol $\nmid$ means does not divide, for example $7 \nmid 19$ means $7$ does not divide $19$)

Now, we will see some important properties of congruence.

If,

$a \texttip{\equiv}{congruent to} b \pmod{N}$, and

$c \texttip{\equiv}{congruent to} d \pmod{N}$

then:

$a \times c \pmod{N} \texttip{\equiv}{congruent to} b \times d \pmod{N}$

$a+c \pmod{N} \texttip{\equiv}{congruent to} b + d \pmod{N}$

$a-c \pmod{N} \texttip{\equiv}{congruent to} b - d \pmod{N}$

Also, for any integers $a$, $b$ and $N$

$a \times b \texttip{\equiv}{congruent to} (a \pmod{N}) \times (b \pmod{N})$

$a + b \texttip{\equiv}{congruent to} (a \pmod{N}) + (b \pmod{N})$

$a - b \texttip{\equiv}{congruent to} (a \pmod{N}) - (b \pmod{N})$

We can remove the above congruence symbols by adding $mod$ operations to both sides of our equations, that is:

$(a \times b)\ mod\ N = ((a\ mod\ N) \times (b \mod\ N))\ mod\ N$

$(a + b)\ mod\ N = ((a\ mod\ N) + (b \mod\ N))\ mod\ N$

$(a - b)\ mod\ N = ((a\ mod\ N) - (b \mod\ N))\ mod\ N$

Now, let us look at the following example involving negative numbers:

$a = -5 \pmod{11}$, what is the minimum positive value of $a$?

Based on what we read so far,

if $a = -5 \pmod{11}$ then $(a - (-5)) | 11$, that is, $(a + 5) | 11$. The minimum positive integer that divides $11$ is $11$, hence $a + 5 = 11 \texttip{\Rightarrow}{follows that} a = 6$

For any number $a,\ b,\ N$ and $b < N$, if $a \texttip{\equiv}{congruent to} b \pmod{N}$ then $a \texttip{\equiv}{congruent to} (b-N) \texttip{\equiv}{congruent to} -(N - b) \pmod{N}$, and the proof is as follows:

$a \texttip{\equiv}{congruent to} b \pmod{N}$                     (subtracting $N$ from both sides we get)

$a - N \texttip{\equiv}{congruent to} (b - N) \pmod{N}$   (we know that $N\ modulo\ N = 0$, hence we can replace $N$ on the left side with $0$)

$a \texttip{\equiv}{congruent to} (b - N) \pmod{N}$        (since  $b < N$, $(b - N)$ is a negative number and we can write that as $-(N-b)$.)

As an example, we can write:

$19 \texttip{\equiv}{congruent to} (19 - 20) \texttip{\equiv}{congruent to} -1 \pmod{20}$, and we can keep on subtracting $20$ from the number to get infinitely many negative numbers.

$19 \texttip{\equiv}{congruent to} -1 \texttip{\equiv}{congruent to} -21 \texttip{\equiv}{congruent to} -41 \pmod{20}$ and so on.

The above properties can make solving certain problems extremely easy for us. We will see how by trying the following problem:

We know the when we divide any number by a given integer $N$ we get a remainder ranging from $0$ to $N-1$. The set of integers $\left\{0,\ 1,\ ...\ , N-1\right\}$ is called the $least\ residue\ system\ \pmod{N}$.

We can illustrate these two concepts with some examples. We know that division by $11$ can leave a remainder of $0$ to $10$.

Therefore,

$Least\ Residue\ System \pmod{11} = \left\{0,\ 1,\ 2,\ 3,\ 4,\ 5,\ 6,\ 7,\ 8,\ 9,\ 10\right\}$

A set of all integers which leave the same remainder modulo $N$ is called a $residue\ class\ \pmod{N}$. Let us understand this using an example.

We know, that integers $-\infty ... -22,\ -11,\ 0,\ 11,\ 22,\ 33\ ... \infty$ leave remainders of $0$ when divided by $11$

Therefore, the infinite set $\left\{-\infty ... -22\, -11,\ 0,\ 11,\ 22,\ 33\ ... \infty\right\}$ is one residue class $\pmod{11}$

Similarly, the set $\left\{-\infty ... -22,\ -10,\ 1,\ 12,\ 23,\ ... \infty\right\}$ is another residue class $\pmod{11}$ since all of them leave a remainder of $1$ when divided by $11$.

Likewise, we can have $11$ different residue classes $\pmod{11}$ each corresponding a remainder of $0\ ... 10$

For any arbitrary integer, $a$, and a divisor $N$, the residue class of $a \pmod{N}$ is the infinite set:
$\left\{-\infty,\ ...,\ a-2N,\ a-N,\ a,\ a + N,\ a + 2N,\ ...,\ \infty \right\}$

If we form a set by choosing a number from each of the possible residue classes, we get a complete residue system.

For example the set:

$\left\{22,\ 100,\ 46,\ 36,\ 59,\ 60,\ 83,\ 29,\ 63,\ 108,\ 76\right\}$ is a complete residue system $\pmod{11}$, that is because:

$22 \texttip{\equiv}{congruent to} 0 \pmod{11}$

$100 \texttip{\equiv}{congruent to} 1 \pmod{11}$

$46 \texttip{\equiv}{congruent to} 2 \pmod{11}$

$...$

$76 \texttip{\equiv}{congruent to} 10\pmod{11}$

Since our set has one representative from each of the possible residue classes, this set is a complete residue system $\pmod{11}$.

We should be able to see clearly that the least residue system is also a complete residue system, since it contains the least non-negative element from each of the classes.

No two numbers in a complete residue system or a least residue system (modulo $N$) will leave the same remainder when divided by $N$.