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.