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

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.

Dr Math says, "The quadratic residues are just the squares modulo n".

Consider a number n. The remainders left when the perfect squares (of numbers less than n) are divided by n are called the quadratic residues modulo n. If you're not a quadratic residue, then you're a quadratic non-residue.

Now, (-a)^2 = (a)^2. Since we're doing all our calculations modulo n, (-a) becomes (n - a). So (n - a)^2 = (a)^2. That means that if a number is a quadratic residue, then it'll be a quadratic residue twice; and if it not a quadratic residue, well, then it will never be a quadratic residue. That is what the specks mean when they say that "x^2 = a (mod n) has either 2q roots, or none".*

What this also means is that there are atmost (n - 1)/2 quadratic residues modulo n. The -1 is there for exculding 0 which makes a fuss while eating his vegetables.

Now, if n is a odd prime (i.e. it is a prime that is not 2), we can further go on to show that a quadratic residue can be a quadratic residue _exactly_ twice. Which then means that there are exactly (p - 1)/2 quadratic residues modulo p, where p is a prime. Note that we don't need to bother with the floor functions et. al., since we know for sure that (p - 1) will be even.


*I am missing one case here. What happens when n is even? Well, for the 'middlemost' a, we have (n - a) = a. For example, (10 - 5) = (5) mod 10. So both the roots will actually be the same a, and there is actually only a single root. Another victory for the vigilant colonelmustard and his troops.

Log in or register to write something here or to contact authors.