How Do You Know When to Use of Equality or of Congruence

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 word 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 postal service.

____________________________________________________________________________

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 to a higher place calculation shows that the values of $x^2$ modulo $m=11$ can but exist $1,3,4,5,9$ . So equations such every bit $x^2 \equiv a \ (\text{mod} \ 11)$ for $a=1,3,4,5,9$ have solutions. For instance, 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 hither 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 unproblematic example). The following lemma and corollary confirm what we encounter in the above example.

Lemma i

$p$

$a$

$p$

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

has no solutions or exactly ii solutions.

Proof of Lemma 1
If equation (i) has no solutions, then we are washed. Suppose information technology has at least one solution, say $x=r$ . We accept $r^2 \equiv a \ (\text{mod} \ p)$ . It follows that $x=-r \equiv p-r \ (\text{mod} \ p)$ is a solution of equation (i) as well.

We claim $x=r$ and $x=p-r$ are singled-out modulo $p$ . To see this, suppose $p-r \equiv r \ (\text{mod} \ p)$ . And so $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 supposition 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 exist shown that any solution of equation (1) must be congruent to ane 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 split i of the two factors (Euclid's lemma). The case $p \ \lvert \ (t-r)$ implies $t \equiv r \ (\text{mod} \ p)$ . The instance $p \ \lvert \ (t+r)$ implies $t \equiv -r \ (\text{mod} \ p)$ . $\blacksquare$

Corollary 2

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

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

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

____________________________________________________________________________

General Case

What almost the full general case of the quadratic congruence equation of the following grade?

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

Of course, nosotros only consider the equations where $\alpha \not \equiv 0 \ (\text{mod} \ p)$ and $p$ is an odd prime number. Information technology turns out that equation (two) can exist replaced past an equivalent congruence equation of the same course as equation (1) in a higher place. So the full general case of equation (two) presents no new problem. We just catechumen equation (two) to its equivalence and solve it accordingly. We now discuss how this is washed.

The coefficient $\alpha$ , the coefficient of the $y^2$ term, has a multiplicative changed modulo $p$ . So multiplying equation (2) past $\alpha^{-1}$ gives the following equation.

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

So nosotros can at present focus on solving equation (three), which has the same solutions equally equation (two). Consider the coefficient of the $y$ term. If the coefficient $\alpha^{-1} \beta$ is even, we tin can complete the square and obtain an equivalent equation of the same grade as equation (one). If the coefficient $\alpha^{-1} \beta$ is odd, then we can add $p$ to information technology and obtain an even coefficient. We tin can so proceed to complete the square every bit 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$ . And then nosotros multiply $4$ across and obtain $y^2+16y+4 \equiv 0 \ (\text{mod} \ 11)$ . The coefficient of the $y$ term is even. Nosotros 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 example, 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 past the inverse, we obtain $y^2+9y+72 \equiv 0 \ (\text{mod} \ 11)$ . We farther reduce $72$ modulo $11$ to go $y^2+9y+6 \equiv 0 \ (\text{mod} \ 11)$ . Note that the coefficient of the $y$ term is odd. And 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 concluding equation in the to a higher place derivation is of the grade $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 number such equally the simple instance above, this approach is workable. For large primes, this requires a lot of computational resources.

To further illustrate the quadratic congruences, nosotros work 3 examples with help from Euler'south Benchmark and from using Excel to practice 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 tin can be translated as a modular exponentiation calculation.

The ciphering for $\displaystyle a^{\frac{p-1}{2}} \ (\text{mod} \ p)$ can be washed directly using an online modular arithmetic estimator or using the fast-powering algorithm (discussed in the post Congruence Arithmetics and Fast Powering Algorithm). For a word and a proof of Euler's Criterion, encounter the post Euler's Criterion.

When Euler's Criterion indicates there are solutions, how do we find the solutions? Nosotros demonstrate using the following examples.

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

According to Euler'due south Criterion, the equation $x^2 \equiv 5 \ (\text{mod} \ 61)$ has solutions since $5^{30} \equiv 1 \ (\text{mod} \ 61)$ . To discover 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 nosotros 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 foursquare (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)$ .