Congruences are an important tool for the study of divisibility.

**Definition.**

Let $m \neq 0$ be an integer.

Two integers $a$ and $b$ are congruent modulo $m$ if $m$ divides $a – b$. We write:

$$a \equiv b \pmod m.$$

We read this as ” $a$ is congruent to $b$ modulo $m$”.

The integer $m$ is called **the modulus**.

If $m$ does not divides $a -b$, then $a$ is **incongruent** to $b$ and we write $ a \not \equiv b \pmod m$.

If $ a \equiv b \pmod m$, then $b$ is a **residue** of $a$ modulo $m$. When $ 0 \le b \le m-1$, then $b$ is called the **least non – negative residue** of $a$ modulo $m$.

Since $a -b$ is divisible by $m$ if and only if it is divisible by $-m$, without loss generality we can focus on the positive modulus and in the hereafter $m$ will be a natural number.

**Definition**.

Let $a \in \mathbb{Z}$. The set $[a] = \{x \in \mathbb{Z} : x \equiv a \pmod m \}$ of all integers that are congruent modulo $m$ to $a$ is called a** residue class modulo** $m$.

All members which are in the same residue class are mutually congruent.

We will first show that each integer falls in one and only one residue class.

**Theorem 1**. Congruences modulo $m$ satisfy:

1.) *refleksive*;

$$\forall a \in \mathbb{Z}, \quad a \equiv a \pmod m,$$

2.) *symmetric*;

$$ \forall a, b \in \mathbb{Z}$$, $$\quad a \equiv b \pmod m \quad $$, $$\quad b \equiv a \pmod m,$$

3.) *transitive*;

$$\forall a, b, c \in \mathbb{Z}$$, $$\quad a \equiv b \pmod m \quad$$, $$\quad b \equiv c \pmod m \Longrightarrow a \equiv c \pmod m$$.

This means, the congruence relation $\equiv \pmod m$ is an equivalence relation on the set $\mathbb{Z}$. Therefore, the residue classes partition the integers.

*Proof.*

1.)If $a \equiv a \pmod m$, then $ m | (a -a)$. Since $0$ is divisible by any integer, that $a \equiv a \pmod m$ is valid.

2.) If $a \equiv b \pmod m$, then $m | (b-a)$. Therefore, $m| (-1) (b-a)$ or $m | (a -b)$, that is, $b \equiv a \pmod m$.

3.) If $ a \equiv b \pmod m$ and $ b \equiv c \pmod m$, then $m | (a -b)$ and $ m| (b-c)$. It follows that $m | a – b + b – c$, that is, $m | a -c$.

Hence $m >0$, every integer falls in one and only one residue class.

There are exactly $m$ residue classes modulo $m$, which is discussed in the following theorem.

**Theorem 2**. Let $m> 0$. There exist exactly $m$ residue classes. In particular,

$$[0], [1], \ldots , [m-1]$$

gives a complete set of residue classes.

There are infinitely many sets of complete residue classes. In particular, a set $\{x_1, x_2, \ldots, x_m \}$ is called a **complete residue system modulo** $m$ if for each integer $y$ there is exactly one $x_j$ such that

$$y \equiv x_j \pmod m.$$

In other words, a complete residue system we obtain so we take by one member of the each equivalence class.

The residue classes have the following important property:

*If one element of the some residue class modulo* $m$ *is relatively prime with* $m$, *then it is and every other element of the same class. *

A **reduced residue system modulo** $m$ is the subset of a complete residue system consisting only those elements that are relatively prime with $m$.

A reduced class modulo $m$ has exactly $\varphi(m)$ elements, where is with $\varphi$ denoted the Euler’s phi-function.

**Theorem 3**. Let $\{x_1, x_2, \ldots, x_m \}$ be a complete residue system modulo $m$, and $\gcd(a, m) =1$. Then $\{ax_1, ax_2, \ldots, ax_m \}$ is also a complete residue system modulo $m$.

The definition of congruence can be represented as:

$$a \equiv b \pmod m \Longleftrightarrow m| a -b $$

$$ \Longleftrightarrow a – b = m \cdot t, \quad t \in \mathbb{Z}$$

$$ \Longleftrightarrow a = b + m \cdot t, \quad t \in \mathbb{Z}. $$

The following theorem gives an equivalent way of looking at congruences.

**Theorem 4**. If $a \equiv b \pmod m$, then $b = a + mt, t \in \mathbb{Z}$, and conversely.

We know that equality can be added, subtracted and multiplied. Analogous properties also apply to congruences, which gives us the following theorem.

**Theorem 5**. If $ a \equiv b \pmod m$ and $c \equiv d \pmod m$, then

a) $a + c \equiv b + d \pmod m$,

b) $a -c \equiv a – c \pmod m$,

c) $a \cdot c \equiv b \cdot d \pmod m$,

and

d) $t \cdot a \equiv t \cdot b \pmod m$, for some $t \in \mathbb{Z}$,

is valid.

We can add, subtract and multiply only those congruences that have the same modulus. We find that the congruence multiplies an integer so that $a$ and $b$ we multiply whit this number, and the modulus remains the same.

**Theorem 6**. If $t \cdot a \equiv t \cdot b \pmod m, t \in \mathbb{Z}$ and $\gcd (t, m) = d$, then

$$a \equiv b \pmod{\frac{m}{d}} $$

is valid.

Specifically, if $t\cdot a \equiv t \cdot b \pmod m$ and $\gcd(t, m) =1$, then $a \equiv b \pmod m$.

Consider that on the concrete example. We take the congruence $ 60 \equiv 15 \pmod{10}$. We divide congruence by $5$. Since $\gcd (10, 15) = 5$, that we obtain $12 \equiv 3 \pmod 2$.

**Definition**. An integer $x$ is said to be a **multiplicative inverse** of $a$ modulo $m$ if $x$ satisfies $ax \equiv 1 \pmod m$.

**Theorem 7**. (Existence of multiplicative inverse) Let $m> 0$ be an integer. Then $a$ has a multiplicative inverse modulo $m$ if and only if $\gcd(a, m) = 1$.

Congruences can also be raised to powers, which provides us with the following theorem.

**Theorem 8**. If $ a \equiv b \pmod m$ and $ n \in \mathbb{N}$, then

$$a^n \equiv b^n \pmod m.$$

Notice that the statement of the Theorem 8. in a trivial way filled for $n =0$. The specified result we can generalize.

**Proposition 1**. Let $f$ be a polynomial with integer coefficients. If $ a \equiv b \pmod m$, then $f(a) \equiv f(b) \pmod m$.

For the divisibility theory of basic importance is the following theorem:

**Theorem 9**. Let $a, b \in \mathbb{Z}$ and $m>0$. The numbers $a$ and $b$ leave the same remainder when divided with $m$ if and only if $a \equiv b \pmod m$.

We will show now how to solve some problems from the divisibility theory, by using congruences.

**Example 1**. Find the remainder when the number $109^{345}$ is divided with $14$.

*Solution*.

By the remainder theorem we have:

$$109 =14 \cdot 7 + 11.$$

It follows:

$$109 \equiv 11 \pmod{14}.$$

By using the theorem 8. we obtain the following:

$$109^{345} \equiv 11^{345} \pmod{14}.$$

From the theorem 9. now it follows that $109^{345}$ and $11^{345}$ leave the same remainder when divided by $14$. Therefore, we must determine the remainder when the number $11^{345}$ is divided by $14$.

Since $11^{345} = \left(11^3 \right)^{115} = (1331)^{115}$, that the requested remainder is equal to remainder when $(1331)^{115}$ is divided by $14$.

We use now the remainder theorem on the pair $(1331, 14)$:

$$1331 = 14 \cdot 95 + 1.$$

It follows:

$$1331 \equiv 1 \pmod{14}.$$

From the theorem 8. now it follows that

$$(1331)^{115} \equiv (1)^{115} \pmod{14},$$

that is,

$$(1331)^{115} \equiv 1 \pmod{14}.$$

Therefore, the remainder when $109^{345}$ is divided by $14$ is $1$.

**Example 2**. Find the remainder when the number $2^{100} + 3^{100} $ is divided by $5$.

*Solution.*

Let $N = 2^{100} + 3^{100}$. Since $2 \equiv -3 \pmod 5$ and $3 \equiv -2 \pmod 5$, that by theorems 5. and 8. follows:

$$2^{100} + 3^{100} \equiv (-3)^{100} + (-2)^{100} \pmod 5.$$

By the theorem 9. we have now that the number $N$ leaves the same remainder when it is divided by $5$ as the number $(-3)^{100} + (-2)^{100}$. Write this number as:

$$(-3)^{100} + (-2)^{100} = [(-3)^4]^{25} + [(-2)^4]^{25} $$

$$= 81^{25} + 16^{25}.$$

Since $$81 \equiv 1 \pmod 5$$ and $$16 \equiv 1 \pmod 5$$, that by theorems 5. and 8. follows:

$$81^{25} + 16^{25} \equiv 1^{25} + 1^{25} \pmod 5 $$

$$ \equiv 2 \pmod 5.$$

Therefore, the number $2^{100} + 3^{100}$ gives the remainder $2$ by dividing with $5$.

Sometimes it is very useful to use the following fact:

If $a \equiv b \cdot c \pmod m$ and $b \equiv d \pmod m$, then $a \equiv d \cdot c \pmod m$.

We will show now how to use this rule.

**Example 3.** Determine the last two digits of the number $2^{100}$.

*Solution*.

The last two digits of the given number are in fact digits of the remainder which we obtain by dividing this number with $100$. Firstly, we will write the given number on the following way:

$$2^{100}=(2^{10})^{10} =1024^{10}.$$

Since $1024\equiv 24 \pmod{100}$, that by the theorem 7. follows $1024^{10} \equiv 24^{10} \pmod{100}$.

Therefore, the requested remainder is equal to the remainder which we obtain by dividing the number $24^{10}$ with $100$. Write this number as

$$24^{10} = (24^2)^{5} = 576^{5}.$$

Since $576 \equiv -24 \pmod{100}$, by the theorem 7. follows:

$$575^5 \equiv (-24)^5 \pmod{100}.$$

The above congruence we write in the following way:

$$575^2 \equiv [(-24)^2]^2 \cdot (-24) \pmod{100}$$

$$\equiv 576^2 \pmod{100}. $$

Since $576^2 \equiv (-24)^2 \pmod{100}$, that by substituting it in the previous congruence, we obtain

$$576^2 \equiv (-24)^3 \pmod{100},$$

that is,

$$576^5 \equiv 576 \cdot (-24) \pmod{100}.$$

Finally. since $576 \equiv (-24) \pmod{100}$, we have

$$576^5 \equiv (-24)^2 \pmod{100} $$

$$\equiv 576 \pmod{100}.$$

Hence the last two digits of $2^{100}$ is $76$.

**Solution to a congruence**

The solution to the congruence $f(x) \equiv 0 \pmod m$, where $f(x)$ is a polynomial with integer coefficients, is each integer $x$ that satisfies this congruence.

If $x_0 \in \mathbb{Z}$ is one solution to the congruence $f(x) \equiv 0 \pmod m$, and $x_1 \equiv x_0 \pmod m$, then $x_1$ is also a solution to the above congruence (by the proposition 1.), that is, the whole class $x_0 \equiv x_1 \pmod m$.

Two solutions $x$ and $x^*$ are **equivalent** if $x \equiv x^* \pmod m$. The number of solutions to a congruence is equal to the number of non- equivalent solutions.

**Example 4**. Solve the following congruence:

$$x^2 + x + 1 \equiv 0 \pmod 3.$$

Solution.

The one obvious solution to the given congruence is $x_0= 1$, because $3 \equiv 0 \pmod 3$. However, a solution to this congruence is also a whole class modulo $3$ to which belongs the number $1$. This means that the solution to the given congruence are all integers that leave the remainder $1$ when are divided by $3$, and all of these numbers are of the form $x = 3t +1, t \in \mathbb{Z}$. We have now:

$$(3t +1)^2 + 3t + 1 + 1 \equiv 0 \pmod 3,$$

that is,

$$3( 3t^2 + 3t + 1) \equiv 0 \pmod 3,$$

and this congruence holds. Therefore, the solution to $x^2 + x + 1 \equiv 0 \pmod 3$ is

$$x \equiv 1 \pmod 3.$$