Quadratic Residues

Right-click here to download this page and the Java Class File


Let p be an odd prime. Let a be an integer relatively prime to p.
We define the Legendre symbol
(a/p)= 1if the congruence x2 ≡ a (mod p) has a solution
= –1if the congruence x2 ≡ a (mod p) has no solution


Theorems:
  1. (a/p) = (b/p) if a ≡ b (mod p)
  2. (a2/p) = 1
  3. (a/p) ≡ a(p–1)/2 (mod p) (This is Euler’s Criterion)
  4. (ab/p) = (a/p) (b/p)
  5. (2/p) = (–1)(p2–1)/8

The Law of Quadratic Reciprocity by Gauss:
Let p & q be distinct odd primes. Then
(p/q)= (q/p)if p ≡ 1 (mod 4) or q ≡ 1 (mod 4)
= –(q/p)if p & q ≡ 3 (mod 4)




1