In number theory, a number a is called a quadratic residue (mod p) if there exists some number q such that q2a (mod p). Otherwise, a is called a quadratic nonresidue (mod p).

For example, working mod 5, we have:

02 = 0 ≡ 0 (mod 5)
12 = 1 ≡ 1 (mod 5)
22 = 4 ≡ 4 (mod 5)
32 = 9 ≡ 4 (mod 5)
42 = 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


(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.