In number theory
, a number a
is called a quadratic residue (mod p
) if there exists some number q
such that q2
). Otherwise, a
is called a quadratic nonresidue
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.