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 <d. 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 <d. 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}