Latest Tweets

Free math worksheets

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:

    \[\begin{aligned} &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 \\ \end{aligned}\]

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.

 

 

Shares