Quadratic Residues

Number theory has a lot of nifty tricks that allow us to prove things that seem very non-trivial. For an example of an elementary one, consider quadratic residues: basically, we ask ourselves if there is any square integer that leaves remainder k when divided by n (which from now on I’ll write as “equivalent to k modulo n,” as mathematicians do).

In elementary school, everybody learns about things like adding and multiplying even and odd integers. For example, multiplying two odd integers gives an odd integer, regardless of what the two multiplicands are. It turns out that this holds for every base. For example, let’s look at 3: if a*b is equivalent to c modulo 3, then every pair of numbers equivalent to a and b modulo 3 – say, a+3k and b+3l – is equivalent to c mod 3, since (a+3k)(b+3l) = a*b + 3kb + 3la + 9lk, where everything but a*b is divisible by 3.

Now, just like some numbers are squares and some are not, some are quadratic residues of a given n and some are not. To find all quadratic residues mod 3, all we need to do is square every number from 0 to 2 and look at the remainder it leaves – or, if you will, its residue class mod 3. We get 0^2 = 0, 1^2 = 1, 2^2 = 4 which is equivalent to 1 mod 3. So it turns out that whatever happens, no square integer is equivalent to 2 mod 3.

In number theory, we often like to look for integer solutions of equations, in which case we call them Diophantine. For example, take x^2 – 7y^2 = 3. If x and y can be any real numbers, then there are infinitely many solutions because we can let y be anything we want, and then solve for x – say, y = 0, x = SQRT(3).

But for a lot of things, we’re more interested in integer solutions, sometimes just because we feel like it, and sometimes because it’s important to other branches of math, like ring theory. In that case, the equation has no solutions. To see why, note that 7y^2 is divisible by 7. So x^2 must be equivalent to 3 mod 7. However, the squares of the numbers 0 to 6 mod 7 are 0, 1, 4, 9->2, 16->2, 25->4, and 36->1, so that 3 is a non-residue mod 7.

I know it looks trivial, but you’re going to have to trust me that it can be a pretty powerful technique and that a big chunk of my thesis is based on it. The trick is mainly to use various theorems to see if p is a quadratic residue of q without squaring every number from 0 to q-1.