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