Question 16.2.1.
For what primes \(p\) is there a solution to \(x^2\equiv k\text{ (mod }p)\text{?}\)
Section 16.2 General Quadratic Congruences
The equation \(x^2+k\) is not the only quadratic game in town. What about other quadratics, such as \(x^2+2x+1\text{?}\) It turns out that we can use something you are already familiar with to reduce the whole game to the following.
Let’s confirm this with a look at general quadratic congruences.
First let’s try computing. As an example, take \(x^2-2x+3\text{ (mod }9)\text{.}\) The Sage function
solve_mod works, if a little naively.Sage note 16.2.2. Commands of more sophistication.
Notice that the
solve_mod command is more complicated than divmod. solve_mod returns a list of tuples, where a tuple of length one has a comma to indicate it’s a tuple. (If you tried to solve a multivariate congruence you would find it returns a longer tuple.)The result shows that \(x^2-2x+3\equiv 0\) (mod \(9\)) has two solutions. But how might I solve a general quadratic congruence?
Subsection 16.2.1 Completing the square solves our woes
The key is completing the square! First let’s do an example.
Example 16.2.3.
Completing the square for \(x^2-2x+3\) is done by
\begin{equation*}
x^2-2x+3=\left(x^2-2x+\left(\frac{2}{2}\right)^2\right)+3-\left(\frac{2}{2}\right)^2=(x-1)^2+2\text{,}
\end{equation*}
so solving the original congruence reduces to solving
\begin{equation*}
(x-1)^2\equiv -2\text{ (mod }n)
\end{equation*}
Then assuming I have a square root \(s\) of \(-2\) (mod \(n\)), I just compute \(s+1\) and I’m done! Go ahead and try this for a few different \(n\text{,}\) including of course \(n=9\text{,}\) with Sage.
Should you not have particularly enjoyed completing the square in the past, here is the basic idea for modulus \(n\text{.}\)
Algorithm 16.2.4. Completing the square modulo \(n\).
To complete the square for \(ax^2+bx+c\equiv 0\text{,}\) the key thing to keep in mind is that we do not actually divide by \(2a\text{,}\) but instead multiply by \((2a)^{-1}\text{.}\) Here are the steps.
- Multiply by four and \(a\text{:}\) \(4a^2x^2+4abx+4ac\equiv 0\)
- Factor the square: \((2ax+b)^2-b^2+4ac\equiv 0\)
- Isolate the square: \((2ax+b)^2\equiv b^2-4ac\)
So to solve, we’ll need that \(2a\) is a unit (more or less requiring that \(n\) is odd), and then to find all square roots of \(b^2-4ac\) in \(\mathbb{Z}_n\text{.}\)
Fact 16.2.5.
The full solution to
\begin{equation*}
ax^2+bx+c\equiv 0\text{ (mod }n)
\end{equation*}
is the same as the set of solutions to
\begin{equation*}
x\equiv(2a)^{-1}(s-b)\text{ (mod }n)\text{, where }s^2\equiv b^2-4ac\text{ (mod }n)\text{.}
\end{equation*}
Note that this means \(\gcd(2a,n)=1\) must be true and that \(s^2\equiv b^2-4ac\) must have a solution.
Example 16.2.6.
Let’s do all this with \(x^2+3x+5\equiv 0\) (mod \(n\)). Notice that \(b^2-4ac=9-20=-11\text{,}\) so this equation does not have a solution over the integers, or indeed over the real numbers. Does it have a solution in \(\mathbb{Z}_n\) for some \(n\text{,}\) though?
In the previous example, note that we could not proceed as over the rational numbers by writing
\begin{equation*}
x^2+3x+5=\left(x-\frac{3}{2}\right)^2+\left(5-\left(\frac{3}{2}\right)^2\right)
\end{equation*}
since there is no element \(3/2\in \mathbb{Z}_n\text{;}\) this motivates part of the multiplication by \(4a\) in Algorithm 16.2.4.
