Quadratic Equations and Residues Modulo N

$Quadratic$ $Congruences!$

A quadratic congruence is of the form $$rx^2 + sx + t \equiv u \pmod m.$$

$Quadratic$ $Residue!!!$

A number which has a square root $\pmod{m}$ is called a $quadratic$ $residue$ $\pmod {m}$

How is this useful in problem solving? Well try finding quadratic residues in $\pmod {4}$ for example. The quadratic residues would be $1^2 \equiv 1 \pmod{4}, 2^2 \equiv 0 \pmod{4}, 3^2 \equiv 1 \pmod{4}, 4^2 \equiv 0 \pmod{4}$

Thus the quadratic residues mod 4 are $0$ and $1$.

If that doesn't answer how quadratic residues can be useful let me give you an example from the jmo. This is usajmo 2011 #1:

Find, with proof, all integers $n$ such that $2^n + 12^n+2011^n$ is a perfect square.

Notice that $2^n + 12^n + 2011^n \equiv (-1)^n + 1^n \pmod{3}$

Let's take a look at quadratic residues mod 3. $1^2 \equiv 1 \pmod{3}, 2^2 \equiv 1 \pmod{3}, 3^2 \equiv 0 \pmod{3}$

Thus in order for $2^n + 12^n + 2011^n$ to be a square integer it must be $0$ or $1 \pmod{3}$

Thus $(-1)^n + 1^n \equiv 0,1 \pmod{3}$. If $n$ is even, then $(-1)^n + 1^n \equiv 2 \pmod{3}$ which is impossible.

Thus $n$ is odd.

We are inspired to try $\pmod{4}$ and it would be convenient if $2^n \equiv 0 \pmod{4}$. The only time this is not the case is when $n=1$. When we check this we see that $2+12+2011 = 2025 = 45^2$ and is thus a solution.

Now we assume that $n > 1$

We take $\pmod{4}$ and see that $2^n + 12^n + 2011^n \equiv (-1)^n \pmod {4}$

From before we deduced that $n$ must be odd. Thus $(-1)^n \equiv -1 \equiv 3 \pmod{4}$

But recall how the quadratic residues mod 4 are $0$ and $1$. Thus, it is impossible for a square number to be $3 \pmod{4}$ meaning that for values $n>1, 2^n+12^n+2011^n$ cannot be a square integer.

Thus, the only solution is $n=1$.

Quadratic Residues

We say $k$ is a quadratic residue modulo $n$ if and only if there exists $a$ such that $a^2\equiv k\pmod{n}$. In other words, $k$ is a perfect square modulo $n$.

We say $k$ is a quadratic non-residue if it is not a quadratic residue. (Why not just non quadratic residue?)

Let's see what we can do with this definition.

Solving Quadratics

Suppose that we have a quadratic $ax^2+bx+c\equiv 0\pmod{n}$. By CRT, it suffices to solve it modulo its prime factors to their respective exponents. However, let's first look at it modulo a prime.

Let's suppose that $p$ is an odd prime, for convenience. If $p$ was $2$, then there would only be two cases to check.

We can then proceed in a similar fashion to how we would in the real numbers. We have $$ax^2+bx+c\equiv 0\pmod{p}.$$ Since $p\nmid a$ (otherwise $a\equiv 0$), multiply by $4a$ to get, $$4a^2x^2+4abx+4ac\equiv 0\pmod{p}.$$

Yep, we can complete the square to get, $$(2ax+b)^2-b^2\equiv -4ac\pmod{p}$$ $$(2ax+b)^2\equiv b^2-4ac\pmod{p}.$$ Thus, $x$ exists if and only if $b^2-4ac$ is a quadratic residue. Now suppose that we have gotten past that point and we know $k^2=b^2-4ac$. We'll come back to this step later. Then, we have $$2ax+b\equiv \pm k\mod{p}$$ $$x\equiv\frac{-b\pm k}{2a}\mod{p}.$$ Note that this is valid because $2$ and $a$ are invertible mod $p$. $p$ was chosen to be odd, and if $a$ wasn't invertible, then $p\mid a$, so $a$ would be $0$, which is not true. This is just like the quadratic formula in the real numbers! The only problem is that sometimes, $b^2-4ac$ is a quadratic nonresidue. This is analogous to the situation when $b^2-4ac$ is negative in the real numbers, so the quadratic is not solvable.

To find out when it is solvable, see here.