# 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}$

# Solving Linear Diophantine Equations

Equations such as the ones in the following list always have solutions in real numbers. When we focus only on integer solutions, they are called linear Diophantine equations. In this post, we discuss how to work with linear Diophantine equations in two unknowns. Specifically we show, given such an equation, how to tell if it has solutions and if it does have solutions, how to describe the complete solution set.

$1638x+357y=819$

$255x - 2261y = 1003$

$78x + 195y=45$

$374x+285y=49$

$21x+10y+25z=26$

$22x_1+15x_2+91x_3+437x_4=255$

As indicated above, we are only interested in integer solutions to the equation $ax+by=c$. So by a solution to $ax+by=c$, we mean a pair of integers $(x,y)$ that satisfies the equation.

Solving linear Diophantine equations is a topic that is an extension of the discussion on Euclidean algorithm and the extended Euclidean algorithm in this previous post.

Here’s the thought process. To solve the linear Diophantine equation $ax+by=c$, where $a$, $b$ and $c$ are integers, the first step is to find the greatest common divisor of $a$ and $b$, using Euclidean algorithm. We use the notation $\text{GCD}(a,b)$ to denote the greatest common divisor. Once we know $\text{GCD}(a,b)$, we would know whether the equation $ax+by=c$ has solutions. If it does have solutions, the same algorithm that derives the GCD will generate a particular solution of the equation (this is the extended Euclidean algorithm). From the particular solution, we can describe completely the solution set of the equation $ax+by=c$. In the next section, we discuss this thought process in greater details.

___________________________________________________________________________________________________________________

How to Find Solutions

We demonstrate the method using the linear Diophantine equation $1638x+357y=819$, the first one in the above list, proving any necessary lemma and theorem along the way. We work our way to Theorem 3 below, which gives a way to describe the complete solution set of any linear Diophantine equation (if it has one solution).

Let $d=\text{GCD}(a,b)$. The equation $ax+by=d$ always has a solution. In fact this statement is called the extended Euclidean algorithm. The solution can be obtained by working backward from the Euclidean algorithm (when we use it to obtain the GCD).

For example, $\text{GCD}(1638,357)=21$. We can trace back the steps in finding the GCD to see that

$1638 \cdot (-5)+357 \cdot 23=21$.

Thus the pair $x=-5$ and $y=23$ is a solution to the equation $1638x+357y=21$. Based on this development, we can see that $1638x+357y=c$ always has a solution as long as $c$ is a multiple of $21$. For example, the equation $1638x+357y=819$ has solutions since we have the following:

$1638 \cdot (-5 \cdot 39)+357 \cdot (23 \cdot 39)=21 \cdot 39=819$.

Thus the pair $x=-195$ and $y=897$ is a solution to the equation $1638x+357y=819$, which is the first linear Diophantine equation listed at the beginning of the post. We summarize this discussion in the following lemma.

Lemma 1

Let $d=\text{GCD}(a,b)$. The linear Diophantine equation $ax+by=c$ has a solution if and only if $d \ \lvert \ c$.

The notation $d \ \lvert \ c$ means that $c$ is divisible by $d$.

Proof of Lemma 1
The above discussion essentially shows the direction $\Longleftarrow$. The extended Euclidean algorithm indicates that $ax+by=d$ has a solution $x=x_0$ and $y=y_0$. If $c=d \cdot k$ for some integer $k$, then $a(x_0 \cdot k)+b(y_0 \cdot k)=d \cdot k$ indicates that the pair $x=x_0 \cdot k$ and $y=y_0 \cdot k$ is a solution to $ax+by=c$.

The direction $\Longrightarrow$ follows from the observation that $d=\text{GCD}(a,b)$ always divides the left-hand side of $ax+by=c$. Thus $d$ must divide the right-hand side as well unless the equation has no solution. $\blacksquare$

It turns out that if we can find one solution to a linear Diophantine equation, we can find infinitely many solutions.

Lemma 2

If the pair $x=x_0$ and $y=y_0$ is a solution to $ax+by=c$, then so is the following number pair

$x=x_0+b \cdot k$ and $y=y_0-a \cdot k$

where $k$ is any integer.

We can prove Lemma 2 by plugging the new solutions into the equation $ax+by=c$. We can also observe that if we increase $x$ by the value of $b$, we increase the left-hand side of the equation by $a \cdot b$. On the other hand, if we decrease $y$ by the amount $b$, we decrease the left-hand side of the equation by $b \cdot a$. The net effect is that the left-hand side of the equation remains unchanged.

Using Lemma 2, the following describes infinitely many solutions of the equation $1638x+357y=819$.

$x=-195+357k$ and $y=897-1638k$ for all integers $k$

But the above solution set is not complete. For example, the number pair $x=-178$ and $y=819$ is also a solution to the equation $1638x+357y=819$, but is not listed above. The following theorem will give the complete solution set.

Theorem 3

Let $d=\text{GCD}(a,b)$. If the pair $x=x_0$ and $y=y_0$ is a solution to $ax+by=c$, then the complete solution set of the equation consists of all the integer pairs $(x,y)$ such that

$\displaystyle x=x_0+\frac{b}{d} \cdot k$

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

where $k$ is any integer.

Proof of Theorem 3

Suppose that the pair $x=x_0$ and $y=y_0$ is a solution to $ax+by=c$. Two points to show. One is that any number pair of the above form is a solution. The other is that any solution is of the above form. To see the first, note that

$\displaystyle a(x_0+\frac{b}{d} \cdot k)+b(y_0-\frac{a}{d} \cdot k)=ax_0+by_0=c$

To see the second point, suppose that the number pair $x=x_1$ and $y=y_1$ is a solution to the equation $ax+by=c$. We have the following.

$ax_0+by_0=c$

$ax_1+by_1=c$

Rearranging and dividing by $d$, we have the following.

$a(x_1-x_0)=b(y_0-y_1)$

$\displaystyle \frac{a}{d}(x_1-x_0)=\frac{b}{d}(y_0-y_1) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)$

Note that the two fractions in the last equation are integers since $d$ is the greatest common divisor of $a$ and $b$. Furthermore $\displaystyle \text{GCD} \biggl(\frac{a}{d},\frac{b}{d}\biggr)=1$. Note that after canceling out all the common prime factors of two numbers, the resulting two numbers should be relatively prime.

Based on equation (1) above, the number $\displaystyle \frac{b}{d}$ divides $\displaystyle \frac{a}{d}(x_1-x_0)$. Because $\displaystyle \text{GCD} \biggl(\frac{a}{d},\frac{b}{d}\biggr)=1$, the number $\displaystyle \frac{b}{d}$ cannot divide $\displaystyle \frac{a}{d}$. So the number $\displaystyle \frac{b}{d}$ must divide $\displaystyle x_1-x_0$. So for some integer $k$, we have:

$\displaystyle x_1-x_0=\frac{b}{d} \cdot k \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2)$

Plug $\displaystyle \frac{b}{d} \cdot k$ into (1), we have $\displaystyle \frac{a}{d} \cdot \frac{b}{d} \cdot k=\frac{b}{d}(y_0-y_1)$. This leads to the following.

$\displaystyle y_0-y_1=\frac{a}{d} \cdot k \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (3)$

Equations (2) and (3) show that the solution $x=x_1$ and $y=y_1$ is of the form given in the theorem. $\blacksquare$

Based on Theorem 3, the complete solution set to the equation $1638x+357y=819$ is the following:

$\displaystyle x=-195+\frac{357}{21} \cdot k=-195+17k$

$\displaystyle y=897-\frac{1638}{21} \cdot k=897-78k$

where $k$ is any integer.

___________________________________________________________________________________________________________________

Recap

A linear Diophantine equation $ax+by=c$ is solvable if and only if $d \ \lvert \ c$ where $d=\text{GCD}(a,b)$.

If a linear Diophantine equation $ax+by=c$ is solvable, solving it involves two steps.

Step 1
We first find a particular solution. We can find one by trial and error if the numbers are not too large. Otherwise, we can apply the extended Euclidean algorithm. Note that if we use the Euclidean algorithm to find $d=\text{GCD}(a,b)$, we can just work backward in the Euclidean algorithm to find a solution to the equation $ax+by=d$, which in terms leads to a solution to $ax+by=c$.

Step 2
Theorem 3 provides a way to desribe the complete solution set of the linear Diophantine equation $ax+by=c$ based on the particular solution that is found in Step 1.

___________________________________________________________________________________________________________________

More Examples

To solve $255x - 2261y = 1003$, we need to find the GCD of $255$ and $2261$ (the negative sign of $2261$ can be dropped). We use the Euclidean algorithm.

$2261=8 \cdot 255+221$

$255=1 \cdot 221+34$

$221=6 \cdot 34+17$

$34=2 \cdot 17+0$

The GCD is $17$, which divides $1003$. So the equation has solutions. We need to find a specific solution. First we work backward from the above divisions to find a solution to $255x - 2261y = 17$. Then we multiply that solution by $59$. Working backward, we get:

$255(-62)-2261(-7)=17$

So the number pair $x=-62$ and $y=-7$ is a solution of $255x - 2261y = 17$. Thus the number pair $x=-62 \cdot 59=-3658$ and $y=-7 \cdot 59=-413$ is a solution of $255x - 2261y = 1003$. Thus the following completely describes the solution set of $85x - 68y = 51$.

$\displaystyle x=-3658-\frac{2261}{17} \cdot k=-3658-133k$

$\displaystyle y=-413-\frac{255}{17} \cdot k=-413-15k$

________________________________

To solve $78x+195y=45$, note that the GCD of $78$ and $195$ is $39$, which does not divide $45$. Thus the equation has no solutions.

________________________________

To solve $374x+285y=49$, first find the GCD of $374$ and $285$. We apply the Euclidean algorithm.

$374=1 \cdot 285+89$

$285=3 \cdot 89+18$

$89=4 \cdot 18+17$

$18=1 \cdot 17+1$

$17=17 \cdot 1+0$

Thus the GCD is 1. So the equation has solutions. To get one specific solution, we work backward from the above divisions and obtain:

$374(-16)+285(21)=1$

Thus $x=-16 \cdot 49=-784$ and $y=21 \cdot 49=1029$ is a specific solution to $374x+285y=49$. The complete solution set is described by:

$x=-784+285k$

$y=1029-374k$

for any integer $k$.

___________________________________________________________________________________________________________________

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