Quadratic Non-Residues

The solutions for $x$ of $ax^2$ $+$ $bx$ $+$ $c$ $=$ $0$ is given by $x$ $=$ $\frac{-b \pm \sqrt{b^2-4ac}}{2a}$. The discriminant is $\Delta$ $=$ $b^2-4ac$. It may be that $\sqrt\Delta$ has no solution in a field of prime numbers. For example $\sqrt 3$ has no solution modulo 7; The only squares are $[0,$$1,$$4,$$2]$. We say that $3$ is a quadratic non-residue over 7. However we can work with these numbers as two dimensional numbers $A$ $+$ $\sqrt\Delta B$ and we can perform arithmetic with them.

Modulo a prime $p$, if a number is a non-quadratic residue it has a Legendre symbol of $-1$. If $p$ divides $a$ then the symbol is $0$. Otherwise the symbol is $1$.

To extend to all odd numbers there is a similar definition for Jacobi symbols. If the Jacobi symbol is $-1$ then we are guaranteed $\sqrt\Delta$ has no solution. If the Jacobi symbol is $1$ then there might be a solution or not.

The Kronecker symbol includes the even numbers, but division by $2$ is easy!.

Calculation of the Jacobi symbol has a very quick algorithm.