quadratic residue modulo p
Let p be a prime and a ∈ ℤ with a ̸≡ 0 mod p. Then a is a quadratic residue modulo p if there exists x ∈ ℤ such that x²≡amodp
quadratic non-residue modulo p
if there are no such x s.t. x²≡amodp
is 0 a quadratic residue or non-residue?
Neither
Legendre symbol (a / p)
Let p be a prime and a ∈ ℤ. The Legendre Symbol (a / p) is defined by
(a/p) = { 1 if a is a quadratic residue modulo p, -1 if a is a quadratic non-residue modulo p, 0 if a ≡ 0 modp
if a ≡ b mod p then (a/p)=
(b/p)
How to calculate quadratic residues and non-residues
- write a table with the CSR modulo p (shift so that its either side of 0, remove 0)
- find x² for the CSR
- find what each x² is congruent to in the CSR
- the numbers in this bottom row are quadratic residues modulo p, any which are absent are non-residues modulo p
Lemma IV.2.1 number of quadratic residues and non-residues
Let p be an odd prime. Then there are precisely 1/2(p-1) quadratic residues modulo p and precisely 1/2(p-1) quadratic non-residues modulo p.
Theorem (EULERS CRITERION)
Let p bee an odd prime and a ∈ ℤ. Then,
(a/p) ≡ a¹/²⁽ᵖ⁻¹⁾ mod p
corollary IV.3.1
Let p be an odd prime and a,b ∈ ℤ. Then,
ab/p) = (a/p)(b/p
corollary IV.3.2
Let p be an odd prime. Then
(-1/p) = (-1)¹/²⁽ᵖ⁻¹⁾ = { 1 if p ≡ 1 mod 4, -1 if p ≡ 3 mod 4
least residue
Let p be an odd prime and a ∈ ℤ. The least residue modulo p of a is the unique integer b such that
(i) -1/2(p-1) ≤ b ≤ 1/2(p-1)
(ii) b≡amodp
How to calculate least residue
find what b is congruent to in the CSR either side of 0
Gauss’ Lemma
Let p be an odd prime, a ∈ ℤ and suppose that a ̸≡ 0 mod p. Consider the following integers:
a, 2a, 3a, … , 1/2(p-1)a
and let µ be the number of these integers that have negative least residue. Then
(a/p) = (-1)^µ
How to use gauss’ lemma to evaluate (a/p)
- write out a table with the CSR (only positive side of 0)
- find the least residues (calculate first a.1, then just add a, if new elements >1/2(p-1) then substract p)
- count the number of -ve residues (µ)
- by gauss’ lemma (a/p)= (-1)^µ
Theorem IV.5.1 Quadratic character of 2
Let p be an odd prime. Then (2/p) = {1 if p ≡ ±1 mod 8, -1 if p≡ ±3 mod 8
(p is congruent only to ±1 and ±3 from 0,±1,±2,±3,4 since p is odd)
lattice point
and element of ℝ² that has integer co-ordinates
Lemma IV.6.2. For geometric version of gauss’ lemma (1)
suppose that 1≤ l ≤1/2(p-1) and that la has negative least residue modulo p. Then there exists a member of Λ whose co-ordinate is l
Lemma IV.6.3 For geometric version of gauss’ lemma (2)
Suppose (l,y)∈ ∈ Λ. Then 1 ≤ l ≤. Then 1 ≤ l ≤ 1/2(p-1) and la has negative least residue.
Λ =
Λ = {(x,y) ∈ R | (x,y) is a lattice point and -1/2p < ax - py < 0
|Λ| =
µ
Geometric representation of µ
µ is the number of lattice points in R that are striclty between the lines ax-py=0 and ax -py = 1/2p
Gauss’ Law of Quadratic Reciprocity
Suppose that p and q are distinct odd primes. Then (q/p) = (p/q) unless p≡q≡3mod4 then (p/q)=-(q/p)
Idea of proof for gauss’ law of quadratic reciprocity
- find a region A in the rectangle R (0 to 1/2 p 1/2 q) where A is defined by -1/2p < qx - py < 0
- Let mu be the number of lattice points in A
- find a region N in the rectangle R (0 to 1/2 q 1/2 p) where B is defined by -1/2q < px - qy < 0
- Let sigma be the number of lattice points in B
- apply a map (x,y)->(y,x) on B to get a region C in R (send lattice points to lattice points)
- combine these regions.
- There is a bijection from the set of lattice points in the remaining two regions
- count the number of lattice points in R (note the two remaining regions = 2k points since bijection) and manipulate.
