Latest Tweets

Solving linear congruences

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.