quadratic residue (thing)

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

For example, working mod 5, we have:

0² = 0 ≡ 0 (mod 5)
1² = 1 ≡ 1 (mod 5)
2² = 4 ≡ 4 (mod 5)
3² = 9 ≡ 4 (mod 5)
4² = 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.