This post is an introductory discussion on the congruence equations of the form where the modulus is an odd prime and the number is relatively prime to . A discussion on the related notion of quadratic residues is found here. Specific algorithms for solving quadratic congruence eqautions with odd prime moduli are discussed in this subsequent post.
We start off with a simple example. Calculate modulo for .
The above calculation shows that the values of modulo can only be . So equations such as for have solutions. For example, the solutions for the equation are and .
On the other hand, the equations for have no solutions.
Also note that whenever and the equation has a solution, the solutions come in pairs.
Let be an odd prime number. Let be an integer that is not divisible by (equivalently relatively prime to ). The object of interest here is the quadratic congruence equation . It turns out that each such equation has exactly two solutions whenever the number and the modulus are relatively prime (as demonstrated in the above simple example). The following lemma and corollary confirm what we see in the above example.
Let be an odd prime number. Let be an integer that is not divisible by . Then the equation
has no solutions or exactly two solutions.
Proof of Lemma 1
If equation (1) has no solutions, then we are done. Suppose it has at least one solution, say . We have . It follows that is a solution of equation (1) too.
We claim and are distinct modulo . To see this, suppose . Then . Because is an odd prime, . So . This implies that . Because , , contradicting the assumption that . Thus , demonstrating that equation (1) has at least two solutions.
It remains to be shown that any solution of equation (1) must be congruent to one of and . Suppose . Then . It follows that . Thus must divide one of the two factors (Euclid’s lemma). The case implies . The case implies .
Let be an odd prime number. The equation has exactly two solutions for many numbers and has no solutions for the other numbers .
For the even prime , the equation is not an interesting one. For , is the only solution. For , is the only solution.
For composite moduli, the quadratic equation can have more than two solutions. For example, has four solutions .
For these reasons, we only work with odd prime moduli for quadratic congruences.
What about the general case of the quadratic congruence equation of the following form?
Of course, we only consider the equations where and is an odd prime. It turns out that equation (2) can be replaced by an equivalent congruence equation of the same form as equation (1) above. So the general case of equation (2) presents no new problem. We just convert equation (2) to its equivalence and solve it accordingly. We now discuss how this is done.
The coefficient , the coefficient of the term, has a multiplicative inverse modulo . So multiplying equation (2) by gives the following equation.
So we can now focus on solving equation (3), which has the same solutions as equation (2). Consider the coefficient of the term. If the coefficient is even, we can complete the square and obtain an equivalent equation of the same form as equation (1). If the coefficient is odd, then we can add to it and obtain an even coefficient. We can then proceed to complete the square as in the even case. We demonstrate with two examples.
Consider the equation . Since . The multiplicative inverse of is . So we multiply across and obtain . The coefficient of the term is even. We complete the square as follows.
The last equation in the above derivation is of the form where the solutions are and . Thus we have and . These two congruences give and .
For the odd case, consider the equation . The multiplicative inverse of is as . After multiplying by the inverse, we obtain . We further reduce modulo to get . Note that the coefficient of the term is odd. So we add modulus to that coefficient to obtain the equation . We then proceed to complete the square as follows.
The last equation in the above derivation is of the form , which has no solutions (based on the simple example above). Thus the original equation has no solutions.
To solve the quadratic congruence , one way is to compute the entire table of values for modulo . For very small prime such as the simple example above, this approach is workable. For large primes, this requires a lot of computational resources.
To further illustrate the quadratic congruences, we work three examples with help from Euler’s Criterion and from using Excel to do some of the calculations.
According to Euler’s Criterion, the equation has solutions if and only if . Equivalently, the equation has no solutions if and only if . So the solvability of the quadratic congruence equation can be translated as a modular exponentiation calculation.
The computation for can be done directly using an online modular arithmetic calculator or using the fast-powering algorithm (discussed in the post Congruence Arithmetic and Fast Powering Algorithm). For a discussion and a proof of Euler’s Criterion, see the post Euler’s Criterion.
When Euler’s Criterion indicates there are solutions, how do we find the solutions? We demonstrate using the following examples.
According to Euler’s Criterion, the equation has solutions since . To find the solutions, we keep adding the modulus to until we get a perfect square.
So we have , which gives and . The solutions are and .
Since , the equation has solutions. We then add the modulus repeatedly to until we get a perfect square (with the aid of an Excel spreadsheet).
So we have , which gives and . The solutions are and .
Since , the equation has no solutions according to Euler’s Criterion.
Revised December 9, 2015