Modular Mathematics, Quadratic Residues

Quadratic Residues

In the context of a fixed modulus m and a specific exponent n, c is a residue if there is some x such that xn = c mod m.  In other words, c has an nth root.  When n is 2, c is a quadratic residue.  When n = 3, c is a cubic residue.  Quartic and quintic residues are defined similarly.  If n is coprime to φ(m), raising to the nth power merely permutes the units.  Thus every unit is a residue with precisely one root.  For instance, every element mod 5 is a cubic residue.  The cube root of 2 is 3, and so on.  Zero is always a residue, and it has precisely one root when m is prime.

The Legendre symbol [a\p] for p prime is 0 if a = 0, 1 if a is a quadratic residue, and -1 if a is not a quadratic residue.

Let r be a primitive root mod p.  The powers of r, from 1 to p-1, cover all the nonzero values.  The even powers of r are the squares, the quadratic residues.  There's an easy way to see if a number is a square.  Anything raised to the 2, then to the (p-1)/2, is really raised to the p-1, and becomes 1.  When r is raised to an odd power, and then to the (p-1)/2, it becomes -1.  Therefore [a\p] is the same as a(p-1)/2.

Using this equivalent formula, [a\p]×[b\p] = [ab\p].  Multiplication distributes across the Legendre symbol.

Let's see what this means when a and b are and are not residues.  The product of squares is a square (that's pretty obvious), a square times a nonsquare is a nonsquare (that's sort of obvious), and the product of nonsquares is a square (that's far from obvious).  For instance, 3 and 5 are not squares mod 7, yet their product, 15, is 1 mod 7, which is certainly a square.