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,b), which is the greatest common divisor of a and b. The following discussion will make clear how to derive the d many solutions.

___________________________________________________________________________________________________________________

Connection with Linear Diophantine Equations

Note that the equation ax+my=c 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 numbers 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}

About these ads

One thought on “Solving Linear Congruences

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s