Solve the following quadratic congruences:
(a) $x^2 + 2x + 2 \equiv 0 \pmod {23}$
(b) $x^2 + 4x + 2 \equiv 0 \pmod {23}$
(c) $x^2 + 6x + 5 \equiv 0 \pmod {23}$
(a) We rewrite the expression by "completing the square".
$$ x^2 + 2x + 2 \equiv (x+1)^2 + 1 \equiv 0 \pmod {23} $$
So we need to solve
$$ (x+1)^2 \equiv 22 \pmod {23} $$
We first use Euler's Criterion (7.5) to test whether 22 is a quadratic residue of 23.
Since $23 \not \mid 22$ and $22^{\frac{23-1}{2}} \equiv (-1)^{11} \equiv -1 \pmod {23}$ and so 22 does not have a square root modulo 23.
(b) We rewrite the expression by "completing the square".
$$ x^2 + 4x + 2 \equiv (x+2)^2 - 2 \equiv 0 \pmod {23} $$
So we need to solve
$$ (x+2)^2 \equiv 2 \pmod {23} $$
We first use Euler's Criterion (7.5) to test whether 2 is a quadratic residue of 23.
Since $23 \not \mid 2$ and $2^{\frac{23-1}{2}} \equiv (2)^{11} \equiv 2048 \equiv 1 \pmod {23}$ and so 2 has a square root modulo 23.
By Proposition (7.3) $(x+2)^2 \equiv 2 \pmod {23}$ has 2 solutions.
The following calculations shows that $(x+2)\equiv 5 \pmod{23}$ is a solution to $(x+2)^2 \equiv 2 \pmod{23}$.
| x+2 | (x+2)^2 mod 23 |
| 1 | 1 |
| 2 | 4 |
| 3 | 9 |
| 4 | 16 |
| 5 | 2 |
We can use Proposition (3.14b) to identify the second solution as $(x+2) \equiv -5 \equiv 18 \pmod {23}$.
So the solutions to the quadratic congruence are $x \equiv 3 \pmod {23}$ and $x \equiv 16 \pmod {23}$.
(c) We rewrite the expression by "completing the square".
$$ x^2 + 6x + 5 \equiv (x+3)^2 -4 \equiv 0 \pmod {23} $$
So we need to solve
$$ (x+3)^2 \equiv 4 \pmod {23} $$
We first use Euler's Criterion (7.5) to test whether 4 is a quadratic residue of 23.
Since $23 \not \mid 4$ and $4^{\frac{23-1}{2}} \equiv (4)^{11} \equiv 4194304 \equiv 1 \pmod {23}$ and so 2 has a square root modulo 23.
By Proposition (7.3) $(x+3)^2 \equiv 4 \pmod {23}$ has 2 solutions.
By insprection $(x+3) \equiv 2 \pmod {23}$ is a solution to $(x+3)^2 \equiv 4 \pmod {23}$.
Proposition (3.14b) tells us the second solution is $(x+3) \equiv -2 \equiv 21 \pmod {23}$.
So the solutions to the quadratic congruence are $x \equiv 22 \pmod {23}$ and $x \equiv 18 \pmod {23}$.