What is the history of quadratic reciprocity and its symbols?

[Greg Bernhardt]

Definition/Summary

A number n is a quadratic residue mod m if there exists some number a which, squared mod m, gives n.

Equations

Definition of the Legendre symbol, for any number a and for any odd prime p:
\left(\frac ap\right)=\begin{cases}<br /> 0&amp;p|a\\<br /> 1&amp;\exists n:n^2\equiv a\pmod p\\<br /> -1&amp;\nexists n:n^2\equiv a\pmod p<br /> \end{cases}

The Legendre symbol is multiplicative:
\left(\frac{ab}{p}\right)=\left(\frac ap\right)\left(\frac bp\right)

The Law of Quadratic Reciprocity, for any odd primes p and q:
\left(\frac qp\right)=(-1)^{(p-1)(q-1)/4}\left(\frac pq\right)

Extended explanation

For example, 0 1 4 5 6 and 9 are quadratic residues mod 10 because the squares of "ordinary" numbers (which are "base 10") can end in 0 1 4 5 6 or 9.

2 3 7 and 8 are not quadratic residues mod 10.

The law of Quadratic Reciprocity, of course, does not apply mod 10, because 10 is not a prime.

A generalisation of the Legendre symbol for odd non-primes p is the Jacobi symbol.

There is also a Hilbert symbol.

There are extensions of the law of Quadratic Reciprocity for non-prime p and q.

* This entry is from our old Library feature. If you know who wrote it, please let us know so we can attribute a writer. Thanks!

 

[fresh_42]

Legendre symbols are an important tool in number theory, and nowadays also in cryptology as some encryption schemes rely on the difficulty of factorization as e.g. RSA.

The theory of congruences was developed by Carl Friedrich Gauss in his 1801 published work "Disquisitiones Arithmeticae". The term congruence was used by Christian Goldbach as early as 1730 in letters to Leonhard Euler, but without the theoretical depth of Gauss. In contrast to Gauss, Goldbach used the symbol $\ mp$ and not $\ equiv$. Even the Chinese mathematician Qin Jiushao already knew congruences and the associated theory, as in his book published in 1247 "Shushu Jiuzhang ("Mathematical treatise in nine chapters').