Quadratic reciprocity

The Jacobi symbol, (m/n), is defined whenever n is an odd number. It has the following properties that enable it to be easily computed.

• (a/n) = (b/n) if a = b mod n.
• (1/n) = 1 and (0/n) = 0.
• (2m/n) = (m/n) if n = ±1 mod 8. Otherwise (2m/n) = _¯(m/n).
• (Quadratic reciprocity) If m and n are both odd, then (m/n) = (n/m) unless both m and n are congruent to 3 mod 4, in which case (m/n) = _¯(n/m).

If n is a prime, then (m/n) = 1 exactly when m is a nonzero square mod n (a quadratic residue).

---