Solving Quadratic Congruences

This post is an introductory discussion on the congruence equations of the form x^2 \equiv a \ (\text{mod} \ p) where the modulus p is an odd prime and the number a is relatively prime to p. 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.

____________________________________________________________________________

Simple Example

We start off with a simple example. Calculate x^2 modulo m=11 for x=0,1,2,\cdots,10.

    0^2 \equiv 0 \ (\text{mod} \ 11)

    1^2 \equiv 1 \ (\text{mod} \ 11)

    2^2 \equiv 4 \ (\text{mod} \ 11)

    3^2 \equiv 9 \ (\text{mod} \ 11)

    4^2 \equiv 5 \ (\text{mod} \ 11)

    5^2 \equiv 3 \ (\text{mod} \ 11)

    6^2 \equiv 3 \ (\text{mod} \ 11)

    7^2 \equiv 5 \ (\text{mod} \ 11)

    8^2 \equiv 9 \ (\text{mod} \ 11)

    9^2 \equiv 4 \ (\text{mod} \ 11)

    10^2 \equiv 1 \ (\text{mod} \ 11)

The above calculation shows that the values of x^2 modulo m=11 can only be 1,3,4,5,9. So equations such as x^2 \equiv a \ (\text{mod} \ 11) for a=1,3,4,5,9 have solutions. For example, the solutions for the equation x^2 \equiv 5 \ (\text{mod} \ 11) are x=4 and x=7.

On the other hand, the equations x^2 \equiv b \ (\text{mod} \ 11) for b=2,6,7,8,10 have no solutions.

Also note that whenever a \ne 0 and the equation x^2 \equiv a \ (\text{mod} \ 11) has a solution, the solutions come in pairs.

____________________________________________________________________________

Quadratic Congruences

Let m be an odd prime number. Let a be an integer that is not divisible by p (equivalently relatively prime to p). The object of interest here is the quadratic congruence equation x^2 \equiv a \ (\text{mod} \ p). It turns out that each such equation has exactly two solutions whenever the number a and the modulus p are relatively prime (as demonstrated in the above simple example). The following lemma and corollary confirm what we see in the above example.

    Lemma 1

      Let p be an odd prime number. Let a be an integer that is not divisible by p. Then the equation

        x^2 \equiv a \ (\text{mod} \ p) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)

      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 x=r. We have r^2 \equiv a \ (\text{mod} \ p). It follows that x=-r \equiv p-r \ (\text{mod} \ p) is a solution of equation (1) too.

We claim x=r and x=p-r are distinct modulo p. To see this, suppose p-r \equiv r \ (\text{mod} \ p). Then p \ \lvert \ (p-2r). Because p is an odd prime, p \not \lvert \ 2. So p \ \lvert \ r. This implies that p \ \lvert \ r^2. Because p \ \lvert \ (r^2-a), p \ \lvert \ a, contradicting the assumption that p \not \lvert \ a. Thus p-r \not \equiv r \ (\text{mod} \ p), 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 x=r and x=p-r. Suppose t^2 \equiv a \ (\text{mod} \ p). Then t^2 \equiv r^2 \ (\text{mod} \ p). It follows that p \ \lvert \ (t-r)(t+r). Thus p must divide one of the two factors (Euclid’s lemma). The case p \ \lvert \ (t-r) implies t \equiv r \ (\text{mod} \ p). The case p \ \lvert \ (t+r) implies t \equiv -r \ (\text{mod} \ p). \blacksquare

    Corollary 2

      Let p be an odd prime number. The equation x^2 \equiv a \ (\text{mod} \ p) has exactly two solutions for \displaystyle \frac{p-1}{2} many numbers a \in \left\{1,2,\cdots,p-1 \right\} and has no solutions for the other \displaystyle \frac{p-1}{2} numbers a \in \left\{1,2,\cdots,p-1 \right\}.

Remark
For the even prime p=2, the equation x^2 \equiv a \ (\text{mod} \ 2) is not an interesting one. For x^2 \equiv 0 \ (\text{mod} \ 2), x=0 is the only solution. For x^2 \equiv 1 \ (\text{mod} \ 2), x=1 is the only solution.

For composite moduli, the quadratic equation x^2 \equiv a \ (\text{mod} \ m) can have more than two solutions. For example, x^2 \equiv 1 \ (\text{mod} \ 8) has four solutions x=1,3,5,7.

For these reasons, we only work with odd prime moduli for quadratic congruences.

____________________________________________________________________________

General Case

What about the general case of the quadratic congruence equation of the following form?

    \alpha y^2+\beta y+\gamma \equiv 0 \ (\text{mod} \ p)  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2)

Of course, we only consider the equations where \alpha \not \equiv 0 \ (\text{mod} \ p) and p 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 \alpha, the coefficient of the y^2 term, has a multiplicative inverse modulo p. So multiplying equation (2) by \alpha^{-1} gives the following equation.

    y^2+\alpha^{-1} \beta y+\alpha^{-1} \gamma \equiv 0 \ (\text{mod} \ p)  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (3)

So we can now focus on solving equation (3), which has the same solutions as equation (2). Consider the coefficient of the y term. If the coefficient \alpha^{-1} \beta is even, we can complete the square and obtain an equivalent equation of the same form as equation (1). If the coefficient \alpha^{-1} \beta is odd, then we can add p 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 3 y^2+4y+1 \equiv 0 \ (\text{mod} \ 11). Since 4 \cdot 3 \equiv 1 \ (\text{mod} \ 11). The multiplicative inverse of 4 is 3. So we multiply 4 across and obtain y^2+16y+4 \equiv 0 \ (\text{mod} \ 11). The coefficient of the y term is even. We complete the square as follows.

    y^2+16y+4 \equiv 0 \ (\text{mod} \ 11)

    y^2+16y+64 \equiv 64-4 \ (\text{mod} \ 11)

    (y+8)^2 \equiv 60 \ (\text{mod} \ 11)

    (y+8)^2 \equiv 5 \ (\text{mod} \ 11)

The last equation in the above derivation is of the form x^2 \equiv 5 \ (\text{mod} \ 11) where the solutions are x=4 and x=7. Thus we have y+8 \equiv 4 \ (\text{mod} \ 11) and y+8 \equiv 7 \ (\text{mod} \ 11). These two congruences give y \equiv 7 \ (\text{mod} \ 11) and y \equiv 10 \ (\text{mod} \ 11).

For the odd case, consider the equation 5 y^2+y+8 \equiv 0 \ (\text{mod} \ 11). The multiplicative inverse of 5 is 9 as 5 \cdot 9 \equiv 1 \ (\text{mod} \ 11). After multiplying by the inverse, we obtain y^2+9y+72 \equiv 0 \ (\text{mod} \ 11). We further reduce 72 modulo 11 to get y^2+9y+6 \equiv 0 \ (\text{mod} \ 11). Note that the coefficient of the y term is odd. So we add modulus to that coefficient to obtain the equation y^2+20y+6 \equiv 0 \ (\text{mod} \ 11). We then proceed to complete the square as follows.

    y^2+20y+100 \equiv 100-6 \ (\text{mod} \ 11)

    (y+10)^2 \equiv 94 \ (\text{mod} \ 11)

    (y+10)^2 \equiv 6 \ (\text{mod} \ 11)

The last equation in the above derivation is of the form x^2 \equiv 6 \ (\text{mod} \ 11), which has no solutions (based on the simple example above). Thus the original equation 5 y^2+y+8 \equiv 0 \ (\text{mod} \ 11) has no solutions.

____________________________________________________________________________

Examples

To solve the quadratic congruence x^2 \equiv a \ (\text{mod} \ p), one way is to compute the entire table of values for x^2 modulo p. 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 x^2 \equiv a \ (\text{mod} \ p) has solutions if and only if \displaystyle a^{\frac{p-1}{2}} \equiv 1 \ (\text{mod} \ p). Equivalently, the equation x^2 \equiv a \ (\text{mod} \ p) has no solutions if and only if \displaystyle a^{\frac{p-1}{2}} \equiv -1 \ (\text{mod} \ p). So the solvability of the quadratic congruence equation can be translated as a modular exponentiation calculation.

The computation for \displaystyle a^{\frac{p-1}{2}} \ (\text{mod} \ p) 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.

Example 1
Solve x^2 \equiv 5 \ (\text{mod} \ 61).

According to Euler’s Criterion, the equation x^2 \equiv 5 \ (\text{mod} \ 61) has solutions since 5^{30} \equiv 1 \ (\text{mod} \ 61). To find the solutions, we keep adding the modulus to a=5 until we get a perfect square.

    \displaystyle x^2 \equiv 5 \equiv 5+61 \equiv 5+2(61) \equiv \cdots \equiv 5+20(61)=1225=35^2 \ (\text{mod} \ 61)

So we have x^2 \equiv 35^2 \ (\text{mod} \ 61), which gives x=35 and x=-35. The solutions are x \equiv -35 \equiv 26 \ (\text{mod} \ 61) and x \equiv 35 \ (\text{mod} \ 61).

Example 2
Solve x^2 \equiv 899 \ (\text{mod} \ 50261).

Since 899^{25130} \equiv 1 \ (\text{mod} \ 50261), the equation has solutions. We then add the modulus repeatedly to 899 until we get a perfect square (with the aid of an Excel spreadsheet).

    \displaystyle x^2 \equiv 899 \equiv 899+50261 \equiv 899+2(50261) \equiv \cdots \equiv 899+4297(50261)=215972416=14696^2 \ (\text{mod} \ 50261)

So we have x^2 \equiv 14696^2 \ (\text{mod} \ 50261), which gives x=14696 and x=-14696. The solutions are x \equiv 14696 \ (\text{mod} \ 50261) and x \equiv -14696 \equiv 35565 \ (\text{mod} \ 50261).

Example 3
Solve x^2 \equiv 13961 \ (\text{mod} \ 50261).

Since 13961^{25130} \equiv -1 \ (\text{mod} \ 50261), the equation has no solutions according to Euler’s Criterion.

____________________________________________________________________________

\copyright \ 2013 - 2015 \text{ by Dan Ma}
Revised December 9, 2015

Advertisements

5 thoughts on “Solving Quadratic Congruences

  1. Pingback: The Legendre symbol | Exploring Number Theory

  2. Pingback: Solving quadratic congruences with odd prime moduli | Exploring Number Theory

  3. Pingback: Number Theory | MA | Study of Everything

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