A congruence statement that involves unknowns is said to be a congruence equation. In this post, we discuss congruence equations of the form where 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 (see Example 3 below).
Take a simple example of . Solving it means finding all integers such that or for some integer . It is clear that is a solution. After one solution is found, there are infinitely many other solutions. For this example, they are for all integers . However, these additional solutions are congruent to modulo . Are there other solutions that are not congruent to modulo ? It turns out there are two more, and . Any solution to is congruent modulo to one of these three solutions, , or . So the linear congruence equation has three distinct solutions.
For the congruence equation , we are interested in finding a set of distinct solutions modulo . Since every integer is congruent modulo to one of the least residues , we can simply narrow our focus by looking for solutions only among the least residues.
So by a solution to the linear congruence , we mean an integer with such that .
The linear congruence may have no solution. If it does have a solution, the number of solutions is , which is the greatest common divisor of and . The following discussion will make clear how to derive the many solutions.
Connection with Linear Diophantine Equations
Note that the equation is another way of stating the linear congruence . 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 , one approach is to solve the corresponding linear Diophantine equation . The approach in solving is discussed in the previous post called Solving Linear Diophantine Equations.
We first work some examples.
The linear congruence is identical to the linear Diophantine equation . So they both have the same solutions. So we focus on solving .
First, find . We carry out the Euclidean algorithm.
Thus . Note that . So the equation has solutions. We need to find a particular solution.
To do that, we first solve . We work backward in the steps of the Euclidean algorithm as follows:
Since , we have . Thus the number pair and is a particular solution of the equation . The general solutions are described by
where is any integer.
To solve the given linear congruence , we only need to use the solutions. The solutions we are interested in are in the range . The solutions are for . Note that the number of solutions is identical to the GCD of and the modulus .
This one has no solutions since . For the same reason, the equation has no solutions.
Just as in Example 1, the first step is to find . We apply the Euclidean algorithm.
So . 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 . So is a particular solution to the given linear congruence equation and its corresponding linear Diophantine equation .
Now the general solution is given by for any integer . The unique solution we look for is where .
In the modular arithmetic of congruence modulo , the product of and is . So we can view as the multiplicative inverse of and vice versa. We can of course use a computer program to construct a multiplication table for congruence modulo 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 is the product where and are prime numbers. The number and is an example for an encryption key for the RSA algorithm. Finding the decryption key entails solving the linear congruence . 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.
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.
Let . The following conditions are equivalent.
- The linear congruence has a solution.
- The linear Diophantine equation has a solution.
Thus the key to solving a linear congruence equation is to first find the GCD of the coefficient of and the modulus . If the GCD divides the constant , we know there is a solution.
If there is one solution, the linear congruence equation has many distinct solutions modulo .
If we carry out the Euclidean algorithm to find the GCD, we can work backward to find a particular solution to the equation . This will lead to a particular solution to the equation , which can be used to describe the many solutions of the given linear congruence equation . Theorem 2 below summarizes this process.
Let . Let be a solution to the linear congruence equation . We have the following:
- The following integers satisfy the given linear congruence equation and are distinct congruent modulo .
Proof of Theorem 2
Since is a solution to the linear congruence, we have for some integer . Thus the number pair and is a particular solution to the linear Diophantine equation . The following describes the complete solution set of .
where is any integer. Now discard the and consider the following:
Clearly these many values satisfy the linear congruence . Moreover, they are distinct modulo since the absolute difference of any two of these values is less than . So the first bullet point is established.
Any number that satisfies the linear congruence must look like where is some integer (see (1) above). We show that is congruent to one of the numbers in (2).
First, look at the case that . By the division algorithm, we have for some integer and some integer with . Now, we have the following calculation:
Now look at the case that . By the division algorithm, we have for some integer and some integer with . So, . We have the following calculation.
The last number is one of the numbers in (2). So the 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 , we can obtain the many solutions by taking the least residues of the numbers in the second bullet point. Thus the third bullet point is established.