Quadratic Congruences
Quadratic congruences assume the form $Ax^2 + Bx + C \equiv 0 \pmod m$, where $A \not\equiv 0 \pmod m$ (otherwise the congruence would be a linear congruence). We will learn methods to evaluate these quadratic congruences. However, we will first restrict our modulus m to being only an odd prime (3, 5, 7, 11, 13, …), or rather, any prime except 2.
First off, we know that there exists an inverse of A, A' (mod p) such that $AA' \equiv 1 \pmod p$, hence it thus follows that the congruence $Ax^2 + Bx + C \equiv 0 \pmod p$ has the solutions as:
(1)Example 1
Convert the coefficient of the term $x^2$ in the congruence $3x^2 + 5x + 7 \equiv 0 \pmod {11}$ into 1.
We can convert this coefficient into 1 by finding the inverse of 3 (mod 11). A modular inverse of 3 (mod 11) is 4. Hence it follows that $(4)3x^2 + (4)5x + (4)7 \equiv 4(0) \pmod {11}$, or rather that $x^2 + 20x + 28 \equiv 0 \pmod {11}$. Reducing the coefficients to least residues we obtain the following quadratic congruence:
(2)Completing the Square for Quadratic Congruences.
For quadratic congruences in the form $x^2 + A'Bx + A'C \equiv 0 \pmod p$, if the term $A'B$ is even, then we can use the technique of "completing the square" to change the form of the quadratic congruence to:
(3)Now suppose that $A'B$ is odd. Since our prime p is restricted to being odd, then we can change the coefficient of x to be $p + A'B$, and thus transform the quadratic congruence to:
(4)In both cases, we have transformed the quadratic congruence into the form $y^2 \equiv d \pmod p$
Example 2
Complete the square for the polynomial $x^2 -4x -4 = 0$.
Recognize that we can only complete the square for polynomials in the form of $ax + by + c = 0$, which is the form we have with $x^2 -4x -4 = 0$. We first take the coefficient, "b" and divide it by 2, to get -2. We then square this to get 4, and then add 4 and subtract 4 to get:
(5)Now we can complete the square to obtain:
(6)Example 3
Complete the square for the quadratic congruence $3x^2 + 6x + 5 \equiv 0 \pmod 7$.
We will complete the square in the same manner as we did with example 2. First, add 7 to the constant 5 to obtain $3x^2 +6x + 12 \equiv 0 \pmod 7$. Now divide the entire lefthand side by 3 to obtain the congruence $x^2 + 2x + 4 \equiv 0 \pmod 7$. Now take the 2, divide it by 2 to get 1, square it to get 1, and add 1 and subtract 1 from the congruence to obtain:
(7)We can also now find solutions. Notice that x = 1 and x = 4 are solutions to this quadratic congruence.
Theorem 1: If p is an odd prime and p ∤ a, then the quadratic congruence x2 ≡ a (mod p) has exactly 2 solutions or 0 solutions.
- Proof: Suppose that the congruence has a solution r, that is $r^2 \equiv a \pmod p$. Then p-r must also be a solution since:
- Also note that p - r ≠ r. If p = r, then $r \equiv p - r \pmod p$, or rather $2r \equiv 0 \pmod p$ and then $r \equiv 0 \pmod p$. But p is an odd prime, so this cannot be true since $(2, p) = 1$.
- Now suppose that s is a solution. It thus follows that $r^2 \equiv s^2 \pmod p$, so by the definition of a congruence, $p \: \mid \: r^2 - s^2$ and $p \: \mid \: (r + s)(r - s)$, so either $p \: \mid \: (r + s)$ or $p \: \mid \: (r - s)$.
- If $p \: \mid \: (r + s)$, then $s \equiv -r \pmod p$, or rather $s \equiv p - r \pmod p$.
- If $p \: \mid \: (r - s)$, then $s \equiv r \pmod p$.
- s, r, and p - r are all least residues. Hence s = r or s = p - r, which are the only solutions to the quadratic congruence.
Note: Theorem 1 is true when the modulus is an odd prime! If the modulus is not an odd prime, then the quadratic congruence may have more than precisely 2 solutions! |