A linear congruence is an equation of the form
$$ax \equiv b \pmod m.$$
Lemma. Solving the congruence $ax \equiv b \pmod m$ is equivalent to solving the linear Diophantine equation $ax – my = b$.
Since we already know how to solve linear Diophantine equations in two variables, we can apply that knowledge to solve linear congruences.
Let $x_0$ be any concrete solution to the above equation. Then $x_0 \equiv b \pmod m$ is valid. If it is now $x_1$ any number from the equivalence class determined with $x_0$, then from $x_1 \equiv x_0 \pmod m$ follows that $ax_1 \equiv ax_0 \pmod m$, so $ax_1 \equiv b \pmod m$, which means that $x_1$ is also the solution to $ax \equiv \pmod m$.
Therefore, if $ax \equiv b \pmod m$ has a solution, then there is infinitely many solutions.
A linear congruence $ax \equiv b \pmod m$ is equivalent to
$$ax -my = b,$$
for some integer $y$.
This is a linear Diophantine equation and it has a solution if and only if $d = \gcd(a, m)$ divides $b$. If this condition is met, then all solutions are given with the formula:
$$x = x_0 + \left (\frac{m}{d} \right) \cdot t, \quad y= y_0 \left (\frac{a}{d} \right) \cdot t,$$
for any integer $t$.
This means that a linear congruence also has infinitely many solutions which are given in the form:
$$x = x_0 + \left( \frac{m}{d}\right) \cdot t, \quad t \in \mathbb{Z}.$$
We must now see how many distinct solutions are there. For this purpose, we take any two solutions from that set:
$$x_1 = x_0 + \left( \frac{m}{d}\right) \cdot k_1,$$
$$x_2 = x_0 + \left (\frac{m}{d}\right) \cdot k_2.$$
We have now:
$$x_0 + \left( \frac{m}{d} \right) \cdot k_1 \equiv x_0 + \left( \frac{m}{d} \right) \cdot k_2 \pmod m$$
$$\left( \frac{m}{d} \right) \cdot k_1 \equiv \left( \frac{m}{d} \right) \cdot k_2 \pmod m.$$
Since $\frac{m}{d}$ divides $m$, that by the theorem 6.
$$k_1 \equiv k_2 \pmod d$$
is valid.
Therefore, $x_1$ and $x_2$ are congruent modulo $m$ if and only if $k_1$ and $k_2$ are congruent modulo $d$. This means that there are exactly $d$ distinct solutions.
Write this in the form of a theorem.
Theorem 1. Let $a$ and $m$ be natural numbers, and $b$ an integer. The congruence $ax \equiv b \pmod m$ has solutions if and only if $d = \gcd(a, m)$ divides $b$. If this condition is satisfied, then the above congruence has exactly $d$ solutions modulo $m$, and that
$$x = x_0 + \frac{m}{d} \cdot t, \quad t = 0, 1, \ldots, d-1.$$
If $d \nmid b$, then the linear congruence $ax \equiv b \pmod m$ has no solutions.
For instance, solve the congruence $6x \equiv 7 \pmod 8$. Since $\gcd(6,8) = 2$ and $2 \nmid 7$, there are no solutions.
From the theorem above follows:
Theorem 2. If the number $m =p$ is a prime number, and if $a$ is not divisible by $p$, then the congruence $ax \equiv b \pmod p$ always has a solution, and that solution is unique.
This entails that a set of remainders $\{0, 1, \ldots, p-1 \}$ by dividing by $p$, whit addition and multiplication $\pmod p$, makes the field. This field is denoted by $\mathbb{Z}_p$.
There are several methods for solving linear congruences; connection with linear Diophantine equations, the method of transformation of coefficients, the Euler’s method, and a method that uses the Euclidean algorithm…
Connection with linear Diophantine equations
The given congruence we write in the form of a linear Diophantine equation, on the way described above.
Example 1. Solve the following congruence:
$$3x \equiv 8 \pmod 2.$$
Solution.
Since $\gcd(3, 2) = 1$, that, by the theorem 1., the congruence has a unique solution.
$3x \equiv 8 \pmod 2$ means that $3x-8$ must be divisible by $2$, that is, there must be an integer $y$ such that
$$\frac{3x-8}{2} = y,$$
that is,
$$3x – 2y = 8.$$
The one particular solution to the equation above is $x_0 = 0, y_0 = -4$, so $3x_0 – 2y_0 = 8$ is valid.
By subtracting obtained equations we have:
$$3(x – x_0) – 2(y – y_0) =0.$$
It follows: $x – x_0 = 2t, t \in \mathbb{Z}$.
Therefore, solution to the congruence $3x \equiv 8 \pmod 2$ is
$$x = x_0 + 2t, \quad t \in \mathbb{Z},$$
that is,
$$x = 2t, \quad t \in \mathbb{Z}$$
or
$$x \equiv 0 \pmod 2.$$
Method of transformation of coefficients
The method of transformation of coefficients consist in the fact that to the given equation we add or subtract a well selected true congruence. In this way we obtain the congruence which also specifies the class that is the solution.
Example 2. Solve the following congruence:
$$7x \equiv 6 \pmod{15}.$$
Solution.
Since $\gcd(7, 15) = 1$, that the given congruence has a unique solution. To the above congruence we add the following congruence
$$0 \equiv 15 \pmod{15}$$
and we will obtain
$$7x \equiv 21 \pmod{15}.$$
By dividing the congruence by $7$, we have
$$x \equiv 3 \pmod{15}$$
or
$$x = 3 + 15t,$$
and that is the solution to the given congruence.
Method that uses the Euclidean algorithm
If we need to solve the congruence $ax \equiv b \pmod p$, we must first find the greatest common divisor $d= \gcd(a,m)$ by using the Euclidean algorithm. To the solution to the congruence $a’v \equiv b’ \pmod{m’}$, where $a’ = \frac{a}{d}, b’ = \frac{b}{d}$ and $m’ = \frac{m}{d}$, can be reached by applying a simple recursive relation:
$$v_{-1}= 0, \quad v_0 = 1, \quad v_i = v_{i-2} – q_{i-1}, \quad i= 1, \ldots, k,$$
where $k$ is the least non-zero remainder and $q_i$ are quotients in the Euclidean algorithm.
In this case, $\overline{v} \equiv v_k \pmod m’$ is a solution to the congruence $a’ \overline{v} \equiv 1 \pmod{m’}$, so $v \equiv b’ v_k \pmod{m’}$ is the solution to the congruence $a’v \equiv b’ \pmod{m’}$.
The solution to the congruence $ax \equiv b \pmod m$ is now given with:
$$x \equiv v + t \cdot m’ \pmod m, \quad t= 0, 1, \ldots, d-1.$$
Example 3. Solve the following congruence:
$$186 \equiv 374 \pmod{422}.$$
Solution.
We must first find $\gcd(422, 186)$ by using the Euclidean algorithm:
$$422 = 186 \cdot 2 + 50$$
$$186 = 50 \cdot 3 + 36$$
$$50 = 36 \cdot 1 + 14$$
$$36 = 14 \cdot 2 + 8$$
$$14 = 8 \cdot 1 + 6$$
$$8 = 6 \cdot 1 +2$$
$$6= 3 \cdot 2$$
Therefore, $\gcd(422, 186) = 2$. Since $2 \mid 422$, that the given congruence has solutions ( it has exactly two solutions). We have $a’ = \frac{186}{2} = 93$, $b’ = \frac{374}{2} = 187$ and $m’ = \frac{422}{2} = 211$.
We need now aplly the above recursive relation:
We obtain that
$$\overline{v} \equiv 59 \pmod{211}$$
is the solution to the congruence
$$93 v \equiv 1 \pmod{211},$$
so,
$$v \equiv 187 \cdot 59 \pmod{211},$$
that is,
$$v \equiv 61 \pmod{211}$$
is the solution to the congruence
$$93 v \equiv 187 \pmod{211}.$$
Finally, solutions to the given congruence are
$$x \equiv 61, 61 + 211, 61 \pmod{422} \equiv 61, 272 \pmod{422}.$$
Solutions we can write in the equivalent form:
$$x_1 = 61 + 422t, \quad x_2 = 272 + 422t, \quad t \in \mathbb{Z}.$$
Euler’s method
The Euler’s method consist in the fact that we use the Euler’s theorem. Given the congruence
$$ax \equiv b \pmod m.$$
Suppose that $\gcd(a, m) =1$. By the Euler’s theorem
$$a^{\varphi (m)} \equiv 1 \pmod m$$
is valid.
Since always
$$b \equiv b \pmod 1$$
is valid, that we obtain
$$a^{\varphi (m)} \cdot b \equiv b \pmod m.$$
By comparing the above congruence with the initial congruence, we can show that
$$x \equiv a^{\varphi (m) -1} \cdot b \pmod m$$
is the solution to the initial congruence.
Example 4. Solve the following congruence:
$$5x \equiv 8 \pmod{13}.$$
Solution.
By using the formula
$$x \equiv a^{\varphi (m) -1} \cdot b \pmod m$$
we obtain
$$x \equiv 5^{\varphi(13) -1} \cdot 8 \pmod{13}.$$
Since $\varphi (13) =12$, that it follows
$$x \equiv 3^{11} \cdot 8 \pmod{13}.$$
We have now:
$$3^{11} \equiv 9 \pmod{13}.$$
By substituting it in $x \equiv 3^{11} \cdot 8 \pmod{13}$ we obtain
$$x \equiv 9 \cdot 8 \pmod{13},$$
that is,
$$x \equiv 7 \pmod{13},$$
and that is the solution to the given congruence.
