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.
Question16.2.1.
For what primes \(p\) is there a solution to \(x^2\equiv k\text{ (mod }p)\text{?}\)
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 note16.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?
Subsection16.2.1Completing the square solves our woes
The key is completing the square! First let’s do an example.
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{.}\)
Algorithm16.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 in this way, 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{.}\)
Fact16.2.5.
Given that \(\gcd(2a,n)=1\text{,}\) the full solution 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 \(s^2\equiv b^2-4ac\) must have a solution.
Example16.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? Try some examples by hand before using the following interact.
In the previous example, note that we could not proceed as over the rational numbers by writing
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. Also 3
I thank Zach Teitler for discussion on this point.
, note that if \(n=k\ell\) is composite and the quadratic reduces to a linear congruence modulo \(k\) or \(\ell\text{,}\) there may be solutions even if \(\gcd(2a,n)> 1\text{;}\) see Exercise 16.8.18.