Quadratic Residues

Jim Hefferon · Elementary Number Theory · Ch. 6

A quadratic residue mod p is a nonzero number that is a perfect square mod p. Exactly half the nonzero residues are squares. The Legendre symbol encodes which are which, and quadratic reciprocity reveals a deep symmetry between different primes.

Squares mod p

For a prime p, the nonzero residues mod p split evenly: (p-1)/2 are quadratic residues (squares), and (p-1)/2 are non-residues. This is because squaring is two-to-one: a^2 ≡ (-a)^2 (mod p).

Scheme

; Find quadratic residues mod p
(define (quadratic-residues p)
  (let loop ((a 1) (qrs (list)))
    (if (>= a p)
        (sort (delete-duplicates qrs) <)
        (loop (+ a 1)
              (cons (modulo (* a a) p) qrs)))))

(define (delete-duplicates lst)
  (cond ((null? lst) lst)
        ((member (car lst) (cdr lst))
         (delete-duplicates (cdr lst)))
        (else (cons (car lst)
                    (delete-duplicates (cdr lst))))))

(display "QR mod 13: ") (display (quadratic-residues 13)) (newline)
(display "QR mod 7:  ") (display (quadratic-residues 7)) (newline)
(display "QR mod 11: ") (display (quadratic-residues 11))

Legendre symbol and Euler's criterion

The Legendre symbol (a/p) equals 1 if a is a QR mod p, -1 if not, and 0 if p divides a. Euler's criterion computes it: (a/p) ≡ a^((p-1)/2) (mod p). This is a fast test for whether a number is a square mod p.

Scheme

; Euler's criterion: (a/p) = a^((p-1)/2) mod p
(define (mod-pow base exp mod)
  (cond ((= exp 0) 1)
        ((even? exp)
         (let ((half (mod-pow base (quotient exp 2) mod)))
           (modulo (* half half) mod)))
        (else (modulo (* base (mod-pow base (- exp 1) mod)) mod))))

(define (legendre a p)
  (let ((result (mod-pow a (quotient (- p 1) 2) p)))
    (if (= result (- p 1)) -1 result)))

(display "(2/7) = ") (display (legendre 2 7)) (newline)   ; 1 (QR)
(display "(3/7) = ") (display (legendre 3 7)) (newline)   ; -1 (NR)
(display "(4/13) = ") (display (legendre 4 13)) (newline)  ; 1
(display "(5/13) = ") (display (legendre 5 13)) (newline)  ; -1
(display "(7/13) = ") (display (legendre 7 13))             ; -1

Quadratic reciprocity (statement)

For distinct odd primes p and q: (p/q)(q/p) = (-1)^((p-1)/2 * (q-1)/2). In words: p is a square mod q and q is a square mod p, unless both are 3 mod 4, in which case exactly one is. This is the "golden theorem" that Gauss proved eight different ways.

Scheme

; Verify quadratic reciprocity for small primes
(define (mod-pow base exp mod)
  (cond ((= exp 0) 1)
        ((even? exp)
         (let ((half (mod-pow base (quotient exp 2) mod)))
           (modulo (* half half) mod)))
        (else (modulo (* base (mod-pow base (- exp 1) mod)) mod))))

(define (legendre a p)
  (let ((r (mod-pow a (quotient (- p 1) 2) p)))
    (if (= r (- p 1)) -1 r)))

(define (check-reciprocity p q)
  (let* ((lpq (legendre p q))
         (lqp (legendre q p))
         (sign (if (and (= 3 (modulo p 4)) (= 3 (modulo q 4))) -1 1)))
    (display "(") (display p) (display "/") (display q) (display ")=")
    (display lpq) (display "  (") (display q) (display "/") (display p)
    (display ")=") (display lqp)
    (display "  product=") (display (* lpq lqp))
    (display "  predicted=") (display sign) (newline)))

(check-reciprocity 3 5)
(check-reciprocity 3 7)
(check-reciprocity 5 7)
(check-reciprocity 3 11)
(check-reciprocity 5 13)

← Chinese Remainder Theorem by june.kim Primitive Roots →