# Solving Linear Congruences

A congruence statement that involves unknowns is said to be a congruence equation. In this post, we discuss congruence equations of the form $ax \equiv b \ (\text{mod} \ m)$ where $x$ is the unknown. These are called linear congruence equations. The goal of this post is to describe a method of solving such equations. As a practical application, the decryption key in the RSA algorithm is obtained by solving the linear congruence equation $ax \equiv 1 \ (\text{mod} \ m)$ (see Example 3 below).

Take a simple example of $12x \equiv 30 \ (\text{mod} \ 9)$. Solving it means finding all integers $x$ such that $9 \ \lvert \ (12x-30)$ or $12x-30=9k$ for some integer $k$. It is clear that $x=1$ is a solution. After one solution is found, there are infinitely many other solutions. For this example, they are $x=1+9j$ for all integers $j$. However, these additional solutions are congruent to $x=1$ modulo $m=9$. Are there other solutions that are not congruent to $x=1$ modulo $m=9$? It turns out there are two more, $x=4$ and $x=7$. Any solution to $12x \equiv 30 \ (\text{mod} \ 9)$ is congruent modulo $m=9$ to one of these three solutions, $x=1$, $x=4$ or $x=7$. So the linear congruence equation $12x \equiv 30 \ (\text{mod} \ 9)$ has three distinct solutions.

For the congruence equation $ax \equiv b \ (\text{mod} \ m)$, we are interested in finding a set of distinct solutions modulo $m$. Since every integer is congruent modulo $m$ to one of the least residues $0,1,2,3,\cdots,m-1$, we can simply narrow our focus by looking for solutions only among the least residues.

So by a solution to the linear congruence $ax \equiv b \ (\text{mod} \ m)$, we mean an integer $x=r$ with $0 \le r \le m-1$ such that $ar \equiv b \ (\text{mod} \ m)$.

The linear congruence $ax \equiv b \ (\text{mod} \ m)$ may have no solution. If it does have a solution, the number of solutions is $d=\text{GCD}(a,m)$, which is the greatest common divisor of $a$ and $m$. The following discussion will make clear how to derive the $d$ many solutions.

___________________________________________________________________________________________________________________

Connection with Linear Diophantine Equations

Note that the equation $ax+my=b$ is another way of stating the linear congruence $ax \equiv b \ (\text{mod} \ m)$. If one has a solution, so does the other (and vice versa). So the linear congruence equation has a solution if and only if the corresponding linear Diophantine equation has a solution (see Theorem 1 below)

To solve the linear congruence equation $ax \equiv b \ (\text{mod} \ m)$, one approach is to solve the corresponding linear Diophantine equation $ax+my=b$. The approach in solving $ax+my=b$ is discussed in the previous post called Solving Linear Diophantine Equations.

___________________________________________________________________________________________________________________

Examples

We first work some examples.

Example 1

Solve $51x \equiv 177 \ (\text{mod} \ 1008)$.

The linear congruence is identical to the linear Diophantine equation $51x+1008y=177$. So they both have the same solutions. So we focus on solving $51x+1008y=177$.

First, find $d=\text{GCD}(51,1008)$. We carry out the Euclidean algorithm.

$1008=19 \cdot 51+39$

$51=1 \cdot 39+12$

$39=3 \cdot 12+3$

$12=4 \cdot 3+0$

Thus $d=\text{GCD}(51,1008)=3$. Note that $3 \ \lvert \ 177$. So the equation $51x+1008y=177$ has solutions. We need to find a particular solution.

To do that, we first solve $51x+1008y=3$. We work backward in the steps of the Euclidean algorithm as follows:

\displaystyle \begin{aligned} 3&=39-3 \cdot 12 \\&=39-3 (51-39)\\&=39(4)+51(-3) \\&=(1008-19 \cdot 51) (4)+51(-3) \\&=51(-79)+1008(4) \end{aligned}

Since $177=3 \cdot 59$, we have $51(-79 \cdot 59)+1008(4 \cdot 59)=3 \cdot 59=177$. Thus the number pair $x=-4661$ and $y=236$ is a particular solution of the equation $51x+1008y=177$. The general solutions are described by

$\displaystyle x=-4661+\frac{1008}{3} \cdot t=-4661+336t$
$\displaystyle y=236-\frac{51}{3} \cdot t=236-17t$

where $t$ is any integer.

To solve the given linear congruence $51x \equiv 177 \ (\text{mod} \ 1008)$, we only need to use the $x$ solutions. The solutions we are interested in are in the range $0 \le r \le 1007$. The solutions are $x=43,379,715$ for $t=14,15,16$. Note that the number of solutions is identical to the GCD of $a=51$ and the modulus $m=1008$.

Example 2

Solve $51x \equiv 689 \ (\text{mod} \ 1008)$.

This one has no solutions since $3 \not \lvert \ 689$. For the same reason, the equation $51x+1008y=689$ has no solutions.

Example 3

Solve $97x \equiv 1 \ (\text{mod} \ 53460)$.

Just as in Example 1, the first step is to find $d=\text{GCD}(97,53460)$. We apply the Euclidean algorithm.

$53460=551 \cdot 97+13$

$97=7 \cdot 13+6$

$13=2 \cdot 6+1$

$6=6 \cdot 1+0$

So $d=\text{GCD}(97,53460)=1$. With Example 1 as a guide, there is only one solution to the given linear congruence.

We work backward in the steps of the Euclidean algorithm to obtain $97(-8267)+53460(15)=1$. So $x=-8267$ is a particular solution to the given linear congruence equation and its corresponding linear Diophantine equation $97x+53460y=1$.

Now the general solution is given by $x=-8267+53460t$ for any integer $t$. The unique solution we look for is $45193$ where $t=1$.

In the modular arithmetic of congruence modulo $53460$, the product of $97$ and $45193$ is $1$. So we can view $45193$ as the multiplicative inverse of $97$ and vice versa. We can of course use a computer program to construct a multiplication table for congruence modulo $53460$ arithmetic. The approach shown here is based on Euclidean algorithm, which is an efficient algorithm for finding inverses.

This example has a connection to the RSA algorithm. The modulus $53460$ is the product $(p-1)(q-1)$ where $p=199$ and $q=271$ are prime numbers. The number $e=97$ and $N=p \cdot q=53929$ is an example for an encryption key for the RSA algorithm. Finding the decryption key entails solving the linear congruence $97x \equiv 1 \ (\text{mod} \ 53460)$. The prime numbers are obviously small and thus not realistic. It is a good practical demonstration of solving linear congruence. For an illustration of RSA, see the post called An Illustration of the RSA Algorithm.

___________________________________________________________________________________________________________________

Discussion

We now prove some theorems to support the above examples. Theorem 1 translates linear congruence into linear Diophantine equation. Theorem 2 shows how to obtain the solutions of a linear congruence equation given a particular solution.

Theorem 1

Let $d=\text{GCD}(a,m)$. The following conditions are equivalent.

1. The linear congruence $ax \equiv b \ (\text{mod} \ m)$ has a solution.
2. The linear Diophantine equation $ax+my=b$ has a solution.
3. $d \ \lvert \ b$.

______________________________________
$\text{ }$
Thus the key to solving a linear congruence equation is to first find the GCD of the coefficient of $x$ and the modulus $m$. If the GCD divides the constant $b$, we know there is a solution.

If there is one solution, the linear congruence equation $ax \equiv b \ (\text{mod} \ m)$ has $d=\text{GCD}(a,m)$ many distinct solutions modulo $m$.

If we carry out the Euclidean algorithm to find the GCD, we can work backward to find a particular solution to the equation $ax+my=d$. This will lead to a particular solution to the equation $ax+my=b$, which can be used to describe the $d$ many solutions of the given linear congruence equation $ax \equiv b \ (\text{mod} \ m)$. Theorem 2 below summarizes this process.

Theorem 2

Let $d=\text{GCD}(a,m)$. Let $x=x_0$ be a solution to the linear congruence equation $ax \equiv b \ (\text{mod} \ m)$. We have the following:

1. The following $d$ integers satisfy the given linear congruence equation and are distinct congruent modulo $m$.
2. $\text{ }$

$\displaystyle x=x_0+\frac{m}{d} \cdot t$ where $t=0,1,2,\cdots,d-1$

3. The $d$ many numbers listed in the first bullet point are the complete solutions in the sense that any number $x$ that satisfies the linear congruence $ax \equiv b \ (\text{mod} \ m)$ is congruent modulo $m$ to one of the numbers in the above bullet point.
4. $\text{ }$

5. The least residues modulo $m$ of the $d$ numbers in the first bullet point are the solutions of the given linear congruence equation $ax \equiv b \ (\text{mod} \ m)$.

$\text{ }$
Proof of Theorem 2

Since $x=x_0$ is a solution to the linear congruence, we have $a \cdot x_0+m \cdot y_0=b$ for some integer $y_0$. Thus the number pair $x=x_0$ and $y=y_0$ is a particular solution to the linear Diophantine equation $ax+my=b$. The following describes the complete solution set of $ax+my=b$.

$\displaystyle x=x_0+\frac{m}{d} \cdot t \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)$

$\displaystyle y=y_0-\frac{a}{d} \cdot t$

where $t$ is any integer. Now discard the $y$ and consider the following:

$\displaystyle x=x_0+\frac{m}{d} \cdot t$ where $t=0,1,2,\cdots,d-1 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2)$

Clearly these $d$ many values satisfy the linear congruence $ax \equiv b \ (\text{mod} \ m)$. Moreover, they are distinct modulo $m$ since the absolute difference of any two of these values is less than $m$. So the first bullet point is established.

Any number $x$ that satisfies the linear congruence $ax \equiv b \ (\text{mod} \ m)$ must look like $\displaystyle x=x_0+\frac{m}{d} \cdot j$ where $j$ is some integer (see (1) above). We show that $\displaystyle x=x_0+\frac{m}{d} \cdot j$ is congruent to one of the numbers in (2).

First, look at the case that $j>0$. By the division algorithm, we have $j=q \cdot d+r$ for some integer $q$ and some integer $r$ with $0 \le r . Now, we have the following calculation:

$\displaystyle x=x_0+\frac{m}{d} \cdot j=x_0+\frac{m}{d} \cdot (q \cdot d+r)=x_0+m \cdot q+\frac{m}{d} \cdot r \equiv x_0+\frac{m}{d} \cdot r \ (\text{mod} \ m)$

Now look at the case that $j<0$. By the division algorithm, we have $-j=q \cdot d+r$ for some integer $q$ and some integer $r$ with $0 \le r . So, $j=(-q) \cdot d+(-r)$. We have the following calculation.

$\displaystyle x=x_0+\frac{m}{d} \cdot j=x_0+\frac{m}{d} \cdot (-q \cdot d-r)=x_0+m \cdot (-q)+\frac{m}{d} \cdot (-r)$

$\displaystyle \equiv x_0+\frac{m}{d} \cdot (-r) \equiv x_0+\frac{m}{d} \cdot (d-r) \ (\text{mod} \ m)$

The last number $\displaystyle x_0+\frac{m}{d} \cdot (d-r)$ is one of the numbers in (2). So the $d$ many numbers in (2) describes all the solutions to the given linear congruence. Thus the second bullet point is established.

Since we focus on the solutions among the least residues modulo $m$, we can obtain the $d$ many solutions by taking the least residues of the numbers in the second bullet point. Thus the third bullet point is established. $\blacksquare$

___________________________________________________________________________________________________________________

$\copyright \ 2013 \text{ by Dan Ma}$