# Explanation: Jacobi Symbol vs. Solvability of Quadratic Congruences

We have introduced the Legendre symbol $\left(\frac ap\right)$ as an indicator, if a given quadratic congruence $x^2(p)\equiv a(p)$ is solvable for a given odd prime number $p,$ and a given integer $a.$

The Jacobi symbol $\left(\frac an\right)$ is a generalization of the Legendre symbol, allowing the case if the number $n$ is not a prime number. A big advantage of this generalization is that it extremely simplifies the calculation of Legendre symbols. It is no more necessary to know the factorization of the number $|a|,$ the knowledge of which was required when applying calculation rules developed for Legendre symbols (see calculating Legendre symbols). Now, we can simply apply the properties of the Jacobi symbol and transform a given Legendre symbol consecutively into a simpler one until we can calculate it directly (see applications of the Jacobi symbol for examples of such transformations).

But does the Jacobi symbol $\left(\frac an\right)$ say anything about the solvability of the congruence $x^2(n)\equiv a(n),$ if $n$ is composite? Not quite and you should be cautious with such conclusions! Namely:

• If $\left(\frac an\right)=-1,$ then the congruence is $x^2(n)\equiv a(n)$ is for sure not solvable. If it was, then $x^2(p)\equiv a(p)$ would be solvable modulo each prime number $p$ dividing $n.$ But in this case, we would have $\left(\frac an\right)=1$ by definition of the Jacobi symbol.
• If $\left(\frac an\right)=1,$ then the congruence might be solvable, but it can also be not solvable! For instance, if $a$ is a quadratic nonresidue modulo a prime $p$ and $n=p^2$, then $\left(\frac an\right)=1,$ but $x^2(n)\equiv a(n)$ is not solvable.

Github: ### References

#### Bibliography

1. Landau, Edmund: "Vorlesungen über Zahlentheorie, Aus der Elementaren Zahlentheorie", S. Hirzel, Leipzig, 1927
2. Blömer, J.: "Lecture Notes Algorithmen in der Zahlentheorie", Goethe University Frankfurt, 1997