Section: Generalizations of the Legendre symbol - Jacobi and Kronecker Symbols

The Legendre symbol $\left(\frac ap\right)$ is only defined for odd prime numbers $p > 2.$ It allows to master the question, whether, for a given integer $a,$ the congruence $x^2(p)\equiv a(p)$ is solvable or not.

It turns out that it is possible to generalize the module $p$ to odd, positive integers $n > 0$ (Jacobi symbol) or even to all integers $n$ (Kronecker symbol), both symbols denoted by $\left(\frac an\right).$ In this section, we will define both symbols and learn to calculate them, without knowing the factorization of $|n|.$

Even though we will be able to calculate the Jacobi or the Kronecker symbols, unfortunately, it will be no more as easy possible to decide, whether the congruence $x^2(n)\equiv a(n)$ is solvable, as it was the case for the Legendre symbol, if the module $n$ is a composite. Nevertheless, the Jacobi symbol has still many applications in modern computational number theory, especially in primality testing and cryptography (for algorithms, see part semi-numerical algorithms). On the other hand, the Kronecker symbol has applications in the classical number-theoretic results of Dirichlet (1805 - 1859).

Explanations: 1

  1. Definition: Jacobi Symbol
  2. Theorem: Properties of the Jacobi Symbol

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

Github:
bookofproofs


References

Bibliography

  1. Landau, Edmund: "Vorlesungen ├╝ber Zahlentheorie, Aus der Elementaren Zahlentheorie", S. Hirzel, Leipzig, 1927