NTIC General Quadratic Congruences

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.

🔗

Question 16.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.

xxxxxxxxxx
 
solve_mod([x^2-2*x+3==0],9)

🔗

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.

xxxxxxxxxx
 
solve_mod([x^2==-2],9)

🔗

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?

xxxxxxxxxx
 
L = [(n,solve_mod([x^2==-11],n)) for n in prime_range(3,100)]
for l in L:
    L1 = [m[0] for m in l[1]]
    modulus = l[0]
    pretty_print(html(r"Modulo $%s$, $x^2\equiv -11$ has the solutions: %s"%(modulus,L1)))
    if L1 != []:
        try:
            LS = [mod(2*1,modulus)^(-1)*(m-3) for m in L1]
            pretty_print(html(r"For each of these, $x\equiv (2\cdot 1)^{-1}(s-3)$: %s"%(LS)))
            LS = [ls^2+3*ls+5 for ls in LS]
            pretty_print(html("And $x^2+3x+5$ gives for each of these: %s\n\n"%(LS)))
        except ZeroDivisionError:
            pretty_print(html("Since 2 doesn't have an inverse modulo $%s$, we can't use this.\n\n"%modulus))

🔗

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.