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).
