In

number theory, a number

`a` is called a quadratic residue (mod

`p`) if there exists some number

`q` such that

`q`^{2} ≡

`a` (mod

`p`). Otherwise,

`a` is called a quadratic

nonresidue (mod

`p`).

For example, working mod 5, we have:

0^{2} = 0 ≡ 0 (mod 5)

1^{2} = 1 ≡ 1 (mod 5)

2^{2} = 4 ≡ 4 (mod 5)

3^{2} = 9 ≡ 4 (mod 5)

4^{2} = 16 ≡ 1 (mod 5)

Hence, ignoring the degenerate case of zero, we say that 1 and 4 are quadratic residues (mod 5), while 2 and 3 are nonresidues.

Mathematicians find the phrase "`a` is a quadratic residue mod `p`" a little unwieldy, so they introduce a shorthand called the Legendre symbol. If the above statement is true, they write:

(`a`/`p`) = 1

E.g., (4/5) = 1

Otherwise:

(`a`/`p`) = -1

E.g., (2/5) = -1

It's actually very interesting, and potentially useful^{*}, to be able to calculate (`a`/`p`), particularly when `p` is prime. This can be very difficult to do simply by squaring and examining (like in our example above); fortunately, this task is made easier by the Law of Quadratic Reciprocity, first proven by Gauss. In my opinion, one of the most beautiful theorems in all mathematics.

^{*} As with much mathematics, "useful" is a relative term; practical applications are not always apparent. However, the theory of residues, including quadratic ones, arises often in the context of cryptography. A quick Google of "quadratic residues application" found, among other things, a proposal for a cryptographic system based on QRs.