1. Jul 23, 2014

### 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} 0&p|a\\ 1&\exists n:n^2\equiv a\pmod p\\ -1&\nexists n:n^2\equiv a\pmod p \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!