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} + 2 x + 1 ?

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 (mod p) ?$

🔗

Let's confirm this with a look at general quadratic congruences.

🔗

First let's try computing. As an example, take

x^{2} - 2 x + 3 (mod 9) .

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} - 2 x + 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} - 2 x + 3$ is done by

x^{2} - 2 x + 3 = (x^{2} - 2 x + {(\frac{2}{2})}^{2}) + 3 - {(\frac{2}{2})}^{2} = (x - 1)^{2} + 2,

so solving the original congruence reduces to solving

(x - 1)^{2} \equiv - 2 (mod n)

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,$ including of course $n = 9,$ 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 .

🔗

Algorithm 16.2.4. Completing the square modulo $n$ .

To complete the square for $a x^{2} + b x + c \equiv 0,$ the key thing to keep in mind is that we do not actually divide by $2 a,$ but instead multiply by $(2 a)^{- 1} .$ Here are the steps.

Multiply by four and $a :$ $4 a^{2} x^{2} + 4 a b x + 4 a c \equiv 0$
Factor the square: $(2 a x + b)^{2} - b^{2} + 4 a c \equiv 0$
Isolate the square: $(2 a x + b)^{2} \equiv b^{2} - 4 a c$

So to solve, we'll need that $2 a$ is a unit (more or less requiring that $n$ is odd), and then to find all square roots of $b^{2} - 4 a c$ in $Z_{n} .$

🔗

Fact 16.2.5.

The full solution to

a x^{2} + b x + c \equiv 0 (mod n)

is the same as the set of solutions to

x \equiv (2 a)^{- 1} (s - b) (mod n), where s^{2} \equiv b^{2} - 4 a c (mod n) .

Note that this means $gcd (2 a, n) = 1$ must be true and that $s^{2} \equiv b^{2} - 4 a c$ must have a solution.

🔗

Example 16.2.6.

Let's do all this with $x^{2} + 3 x + 5 \equiv 0$ (mod $n$ ). Notice that $b^{2} - 4 a c = 9 - 20 = - 11,$ so this equation does not have a solution over the integers, or indeed over the real numbers. Does it have a solution in $Z_{n}$ for some $n,$ 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))