Explanation: Jacobi Symbol vs. Solvability of Quadratic Congruences

(related to Section: Generalizations of the Legendre symbol - Jacobi and Kronecker Symbols)

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:

Thank you to the contributors under CC BY-SA 4.0!




  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