CH 7 Quadratic reciprocity Flashcards
We have learned how to solve linear congruences:
for instance, 2x ≡ 3 (mod 13).
2x ≡ 3 (mod 13).
Here, since gcd(2, 13) = 1, we have 2a + 13b = 1 for e.g. a = 7, b = −1, hence 2 · 7 ≡ 1
(mod 13), and so 7 · 2x ≡ x ≡ 7 · 3 ≡ 8 (mod 13)
n quadratic equations: can we find a solution of x^2 ≡ 2 (mod 13)?
answer is no (just check all possible values for x!). Only some numbers are congruent to squares modulo 13. Figuring out which ones helps solving other quadratic
congruences too
def 7.1.2
quadratic residue
Fix a, m integers with m >=2
a is a quadratic residue mod m
if there exists x in Z with
x^z≡ a mod m
Otherwise, we call it quadratic
non-residue
e.g quadratic residues mod 8:
0,1,4 mod 8
2,3,5,6 arent QR mod 8
01 QR mod 4
0,1 are always
2 dep on number
example:lecture only
quadratic residues mod 3
mod 5
mod 7
mod 3
0,1 are
2 is not
mod 5 0,1,4 are
2,3 arent
mod 7
0,1,4,2 are
3,5,6 arent
note approx half are
reason
skipped then done
Example 7.1.1. We want to find x such that
2x^2 + x + 1 ≡ 0 (mod 13).
Multiply everything by 7 (because 7x1 congruent to 1 mod 13)
so that the equation becomes
x^2 + 7x + 7 ≡ 0 (mod 13).
Now a trick: replace 7 with 20 (mod 13), so its even and complete the square.
(x+10)^2-100+7 ≡ 0
(x+10)^2-2 ≡ 00 mod 13
problem is that
(2/13)=-1 (legendres) is not a QR
(We find
x^2 + 7x + 7 ≡ x
2 + 20x + 7 = (x + 100)
2 − 100 + 7 ≡ (x + 100)
2 − 2 ≡ 0 (mod 13).
But we have just said that no square is congruent to 2 modulo 13, so the original congruence has no solution.
skipped
Example 7.1.3. Let us compute all possible squares modulo 13 (beyond 0, which is
obviously a quadratic residue):
1^2 ≡ 12^2 ≡ 1, 2^2 ≡ 11^2 ≡ 4, 3^2 ≡ 10^2 ≡ 9,
4^2 ≡ 9^2 ≡ 3, 5^2 ≡ 8^2 ≡ 12, 6^2 ≡ 7^2 ≡ 10.
Hence 1, 3, 4, 9, 10, 12 are quadratic residues modulo 13, and since we have done all
possible squares, 2, 5, 6, 7, 8, 11 are quadratic non-residues
exactly half of them
PROPn
7.1.4
how many quadratic residues?
If p is an odd prime, then half of the numbers in {1, 2, . . . , p − 1} are quadratic residues, and the other half consists of quadratic non-residues.
proof
If p is an odd prime, then half of the numbers in {1, 2, . . . , p − 1} are quadratic residues, and the other half consists of quadratic non-residues.
Proof.
Pick r primitive root of p, Then r^k is a quadratic residue
then r^k congruent to x^2 (due to primitive root)
congruent to (r^l)^2 mod p
this means k congruent to 2l mod p-1
when you use a primitive root, if two powers are congruent mod p then exponents are congruent mod p-1
if p=2 nothing to do
p>2 then k is even
If k is even then
r^k = (r^{k/2})^2 is a quadratic residue
every number between 1 and p-1 is congruent toa power r^k
QR are exactly ones where k is even
so result (p-1_/2
proof
The quadratic residues are the remainders of 1², 2²
, . . . ,(p − 1)² modulo p.
Moreover, each remainder occurs exactly twice, because x
2 ≡ y² (mod p) happens
if and only if
p | (x + y)(x − y)
if and only if
p | (x + y) or p | (x − y), and in the
range {1, 2, . . . , p − 1},
this happens exactly when either x = y or x = p − y (and the
two options are mutually exclusive because p is odd).
Exercise 7.1.5 (⋆⋆, in exercise sheet). Let a, b, c, n be integers with n > 1 and gcd(2a, n) =
1. Show that the congruence ax2 + bx + c ≡ 0 (mod n) has a solution if and only if
b
2 − 4ac is a quadratic residue modulo n.
Verify in particular that all the solutions are of the form e(−b + D), where D2 ≡ b
2 −
4ac (mod n) and 2ae ≡ 1 (mod n) (note the similarity with the usual −b±
√
b
2−4ac
2a
).
sheet
Definition 7.2.1 (The Legendre symbol)
Let p be a prime and a an integer with gcd(a,p)=1
we write
{a}
{_}
{p}
:=
{1 if a is a quadratic residue modulo p,
{1 o/w
keeps track of QR
e.g _ is a primitive root mod 7
3 is
all numbers {1,2,…6} are congruent to the powers of 3
3^1≡3 non QR etc
3^2 ≡2 QR even powers
3^3≡6
3^4≡4 QR
3^5≡5
3^6≡1 QR
Example 7.2.2. Repeating Example 7.1.3, we have
(1)
(-)
(13)
= (1/13) notation here
(1/13)=(3/13)=(4/13)=(9/13)=(10/13)=(12/13)
=1 QR
(2/13)=(5/13)=(6/13)=(7/13)=(8/13)=(11/13)
=-1 NOT
qr mod 7 notation legendres symbol
(1/7) = (4/7) =1
(3/7)=-1 etc not QR
Lemma 7.2.3 for legendres symbols
USING LEGENDRES SYMBOL
Let p be an odd prime and a, b be integers not divisible by p. Then:
(1) if a ≡ b (mod p), then (a/p)=(b/p)
2) (a^2/p)=1
3) (a/p) ≡ a ^ ((p-1)/2) eulers criterion
4) (ab/p)= (a/p)(b/p) multiplicativity
4) product of 2 QR is QR
PROOF 3
USING LEGENDRES SYMBOL
Let p be an odd prime and a, b be integers not divisible by p. Then:
(1) if a ≡ b (mod p), then (a/p)=(b/p)
2) (a^2/p)=1
3) (a/p) ≡ a ^ ((p-1)/2) eulers criterion
4) (ab/p)= (a/p)(b/p) multiplicativity
4) product of 2 QR is QR
1,2 IMMEDIATE
3) Fix r primitive root a≡r^k mpd p for some k
if a quad residue then:
k is even
thus
a ^{(p-1)/2) ≡ (rᵏ)⁽ᵖ⁻¹⁾/²
as k is even
≡ (r⁽ᵖ⁻¹⁾ᵏ/² ≡1
as r⁽ᵖ⁻¹⁾≡1
Flittle thm we dont even use the fact of primitive root
if aᵖ⁻¹⁾ᵏ/² ≡1 1 then (rᵏ)⁽ᵖ⁻¹⁾/² ≡1
then
(p-1)| k (p-1)/2
meaning k is even
so =1 IFF quadratic residue
Final step
Otherwise
(a⁽ᵖ⁻¹⁾/² )² ≡a⁽ᵖ⁻¹⁾≡1
so
a⁽ᵖ⁻¹⁾/²≡+-1
Notes say: fix
Y equal to a ^ ((p-1)/2)
By FLT y^2 congruent to 1 mod p
Thus p divides y^2 -1
So y is congruent to + or -1 mod p
We see which one holds for what scenario :
- if a is a quadratic residue then a congruent to x^2 mod p
Then a^(p-1)/2 congruent to
x^2(p-1)/2 Congruent to
x^(p-1)
Congruent to 1 by FLT
CONVERSELY
suppose
a^(p-1)/2 congruent to 1 mod P
Let r be a primitive root mod p
Then a congruent r^k for some k
So
r^(k(p-1)/2) congruent to 1
Mod p
Thus
P-1 divides k(p-1)/2
So k must be even
But then
a congruent to
r^k
Equals
(r^(k/2) )^2
So is a quadratic residue
example
let n,a,b,c integers
gcd(2a,n)=1
(no odd and a coprime to n)
Show that
ax^2+bx+c=0 mod n has a solution in mZ
IFF
b^2-4ac is a quadratic residue mod n
Idea is that sols are given by a formula, knowing which numbers are squares mod n will help here….
exercise?
where does law of reciprocity come from
Computing (a/p) reduces to finding a^{(p−1)/2) modulo p, but that can be hard to do by hand with large numbers. There are many cases, however, in which the computation can gomassively faster
Theorem 7.3.1 (Gauss’ law of reciprocity, art. 151)
USING LEGENDRES SYMBOL HERE
Let p, q be distinct odd primes.
Then
(p/q) = (q/p)
unless
p ≡ q ≡ 3 (mod 4),
in which case
(p/q) = −(q/p).
Equivalently
(p/q)(q/p) = (-1)⁽ᵖ-¹⁾⁽ᵠ-¹⁾/⁴
he wrote:
(p/q) = (-1)⁽ᵖ−¹⁾⁽ᵠ−¹⁾/⁴ (q/p)
———————-
ᵠ means q here*
if we know p is a quadratic residue mod q then we know q mod p is if we dont have p ≡ q ≡ 3 (mod 4)
the equiv part:
-1 exactly when p ≡ q ≡ 3 (mod 4)
Theorem 7.3.2 (Supplementary laws)
to Gauss’ law of reciprocity
LEGENDRES SYMBOL
Let p be an odd prime. Then
(-1/p)=
{1 if p ≡ 1 (mod 4)
{−1 if p ≡ 3 (mod 4)
and
(2/p)
=
{1 if p ≡ ±1 (1,7 mod 8 on board) (mod 8)
{−1 if p ≡ ±3 (mod 8) (0/w on board)
Equivalently,
(-1/p)=(-1)⁽ᵖ−¹⁾/²
and
(2/p) =(-1)^((p^2-1)/8)
first assertion is the old Corollary 2.3.3.
Example 7.3.3
legendre symbol
compute
(2/23/)
Example 7.3.3. 23 is of the form 8k + 7, that is, 23 ≡ −1 (mod 8), so (2/23) = 1. Indeed,
5^2 = 25 ≡ 2 (mod 23).
legendre symbol
compute
(2223/3779)
computes 2223 is a quadratic residue modulo 3779
can’t be done by hand: use quaratic reciprocity and the multiplicative rule
3779 is a prime
2223 isnt (sum of digits is 9, divisible by 3)
the rule can only be used if both are prime
factorising 2223= 3^2 13 19
so =
(3²/3779)(13/3779)(19/3779)
is 3^2 congruent to a square mod 3779? Yes it’s already one!
13 using quadratic reciprocity now as both are odd primes:
we now check if congruent to 3 mod 4:
13≡1 mod 4 :)
19≡3 mod 4
3779≡3 mod 4
=(1)(3779/13)(-1)(3779/19)
(because 13 ≡ 1 (mod 4), while 3779 ≡ 19 ≡ −1 (mod 4). Now we reduce modulo respectively 13 and 19:)
=(-1)(9/13)(-2/19) =(-1)(1)(-2/19)
9 is squared so it is a QR mod 13
=(-1)(-1/19)(2/19)
=(-1)(-1)(-1) = -1
by supplementary laws
19 ≡3 mod 4
19≡3 mod 8
so 223 is not a QR mod 3779
SIMPLE!! Better than computing by hand
so x^2 ≡ 2223 (mod 3779) has
no solution.
Exercise 7.3.5. Compute (12703/16361) (both numbers are prime).
skipped?
We have 16361 ≡ 1 (mod 4), 12703 ≡ 3 (mod 4), 12703 ≡ −1
(mod 8), so
(12703/16361)=
(16361/12703)=
(3658/12703)=
(2/12703)=
(2/12703)(31/12703)(59/12703)
=(31/12703)(59/12703)
=(-1)(12703/31)(-1)(12703/59)
=(24/31)(18/59)
=(2^3/31)(3/31)(2/59)(3^2/59)
=(2/31)(3/31)(2/59)
=1(3/31)(-1)
=(31/3)
=(1/3)=1
where we also have used that 31 ≡ 59 ≡ 3 (mod 4), 31 ≡ −1 (mod 8), 59 ≡ 3
(mod 8). Thus 12703 is a quadratic residue modulo 16361.
Lemma 7.3.6 (Gauss’ lemma, 1808).
Legendre symbol for a/p
With odd prime and a an integer comprime
Let p be an odd prime and a an integer with
gcd(a, p) = 1. Let
S =
{a, 2a, 3a, . . . , [(p − 1)/2]a},
(multiples of a)
and let n be the number of elements of S whose remainder modulo p is strictly larger than p/2. Then
(a/p)= (−1)ⁿ
Example of gauss’ lemma
7.3.7
a = 5, p = 13.
q: is 5 a QR mod 13?
q: is 5 a QR mod 13?
we could use reciprocity maybe but using lemma
S = {5, 10, 15, 20, 25, 30}.
Taking the remainders modulo 13 we find
{5, 10, 2, 7, 12, 4}.
Of these, n = 3 are larger than 13/2, thus
(a/p)=(3/13)=(-1)
matching quadratic reciprocity answer:
q: is 5 a QR mod 13?
quadratic reciprocity answer:
(5/13) = (13/5) we can use as odd primes both congruent to 1 mod 3
13 congruent to 3
=(3/5) Quadratic reciprocity
=(5/3)
=(2/3)=-1
agrees with gauss’ lemma answer
PROOF
Proof of Lemma 7.3.6. GAUSS’
Let p be an odd prime and a an integer with
gcd(a, p) = 1. Let
S =
{a, 2a, 3a, . . . , [(p − 1)/2]a},
(multiples of a)
and let n be the number of elements of S whose remainder modulo p is strictly larger than p/2. Then
(a/p)= (−1)ⁿ
Rearrange S as
S≡{r_1,…,r_m, s_1,…s_n}
where
0<r_i<p/2
p/2<s_j<p
Note n+m=(p-1)/2
Observe numbers are all distinct:
if ua ≡ va mod p
then p|(u-v) (a coprime to p so u ≡v, u and v in this particular set are numbers up to (p-1)/2 so difference can never be divisible by p unless taking same number twice)
so u=v when 0<u,v<(p-1)/2
Not just distinct but also
taking r_i and p-s_j these are both distinct
again if ua≡-va mod p
then p|(u+v)
impossible since 2=< u+v< p-1
s0 {r_1,r_m, p-s_1,…,p-s_n
={1,2,3,…,p-1)/2} as have to be distinct
so (p-1)/2 ! ≡ r_1-r_m(p-s_1)…(p-s_n)
≡r_1….r_ms_1…s_n(-1)^n
using what we know about the elements
≡a^{(p-1)/2}( (p-1)/2)! (-1)^n
1≡ a^{(p-1)/2}(-1)^n mod p
1≡(1/p)(-1)^n as required
notes have some more info…
SUMMARY CH7
main tools
Legendre symbol for p prime gcd(a,p)=1
(a/p) shows if the number is a quadratic residue(QR) mod p
=
{1 if there exists x s.t a≡x² mod p
{-1 otherwise
(a ≡ some perfect square)
Quadratic reciprocity LEARN BY HEART?
p,q odd primes
(p/q) = (-1)^{…} (q/p)
where …= (p-1)(q-1)/4
correction term dep whether they are congruent to 1 or 3 mod 4
supplement laws
(used when prime is even)
(2/p)=(-1)^((p²-1)/8)
(-1/p)=(-1)^{(p-1)/2}
Gauss Lemma
S={a,2a,…,((p-1)/2)a}
n=#{(p/2)<s<p s≡va in S }
Then (a/p)= (-1)^n
so if n even or n off affects if a QR
Proof of the Supplementary laws.
case: (-1/p) corollary 2.3.3
For (2/p): Gauss lemma a=2
S = {2, 4, 6, . . . , p − 1}. How many
elements are strictly bigger than p/2?
- if p = 8k + 1, then S = {2, 4, . . . , 4k, 4k + 2, . . . , 8k}, so 2k;
(p/2=4k+0.5) 2k from counting half the elements
(2/p)=(-1)^2k =1 as 2k even - if p = 8k + 3, then S = {2, 4, . . . , 4k, 4k + 2, . . . , 8k + 2}, so 2k + 1;
as 2k+1 odd
(2/p)=(-1)^{2k+1} =-1 - if p = 8k + 5, then S = {2, 4, . . . , 4k + 2, 4k + 4, . . . , 8k + 4}, so 2k + 1;
- if p = 8k + 7, then S = {2, 4, . . . , 4k + 2, 4k + 4, . . . , 8k + 6}, so 2k + 2.
Thus p ≡ 1 or p ≡ 7 imply (2/p) = 1, otherwise (2/p) = −1.
For the equivalent forms, just check that - (−1)^{p−1/2} = 1 if and only if (p−1)/2
is even if and only if 4 | (p − 1) if and only if
p ≡ 1 (mod 4); - (−1)^{p²−1)/8} = 1 if and only if p²−1)/8is even if and only if 8 | (p + 1) or 8 | (p − 1)
(because one of p−1^2,(p+1)/2 =(p−1)/2 + 1 must be odd).
Proposition 7.4.1. If q = 2n + 1 is an odd prime and q ≡ ±1 (mod 8), then
Proposition 7.4.1. If q = 2n + 1 is an odd prime and q ≡ ±1 (mod 8), then q | (2ⁿ − 1) and in particular (2ⁿ-1 not prime)
consequence for Mersenne primes
Proof. We have q | (2ⁿ − 1) if and only if 2ⁿ ≡ 1 (mod q), thus 2^{(q−1)/2} ≡ 1 (mod q).
By Euler’s criterion, this happens if and only if (2/q) = 1, thus if and only if q ≡ ±1(mod 8) (1 or 7 mod 8)by the Supplementary laws.
M_11 = 2^11 − 1 prime? mersenne prime?
is not prime, because q = 23 = 2 · 11 + 1 is
congruent to −1 modulo 8. Similarly
M_23
M_83
M_131 ,.. are composite
these are special cases
Proposition 7.4.2. primes of the form 8k + 7?
Proposition 7.4.2. There are infinitely many primes of the form 8k + 7.
proof skipped?
read it, uses supplementary laws whether it is QR or not
supposing by contradiction, these proofs might be in exam??
suupose p_1,…,p_n complete list of the form 8k+7 primes
Let N=(p_1…p_n)^2 -2
Since each p_i ≡ -1 mod 8 we have p_1…p_n ≡ +1 or -1 mod 8
thus (p_1…p_n)^2 ≡1 mod 8
N≡-1 mod 8
p_i doesnt divide N for each i since N ≡-2 not congruent to 0 mod p_i
if q is a prime not in our list dividing N then q not equal to 2 since N is odd and
(p_1…p_n)^2 ≡2 mod q
meaning (2/q) =1 therefore q≡ +1 or -1 mod 8 by supplementary laws
but as q not in list of primes of the form 8k+7 mist have q≡1 mod 8
Since this holds for every prime dividing N, we must have N ≡ 1 (mod 8), a contradiction
Proposition 7.4.3. primes of the form 3k + 1.
Proposition 7.4.3. There are infinitely many primes of the form 3k + 1.
Proposition 7.4.3. There are infinitely many primes of the form 3k + 7.
PROOF
MAYBE IN EXAM
CLAIM:
(-3/p)=1 IFF
p≡1 mod 3
for p>3
proving this:
(-3/p)=(-1/p)(3/p)
now by quadratic reciprocity
=(-1)^{(p-1)/2)}(-1)^{((p-1)/2)(3-1)/2} (p/3)
=(-1)^((p-1)/2 + (p-1)/2) (p/3)
=(-1)^{(p-1)}(p/3) =(p/3)
(p/3)=1 IFF p ≡0,1 mod 3
so claim proved.
Suppose p_1,..,p_n is a complete list of primes of the form 3k+1
N= 4(p_1…p_n)^2 +3
N is not divisible by 2, number even
N not divisible by 3 : primes are congruent to 1 mod 3, times by 4 then add 3 not divisible by 3
N not divisible by p_1,…,p_n ,none of them are 3
Take q|N prime (some other prime not in our list)
Then q not equal to 2 or 3 and q not equal to any prime in our list already
N= 4(p_1…p_n)^2 +3≡0 mod q
ie. -3 ≡ (2p_1…p_n)^2
Hence Legendre symbol (-3/q)=1 so q ≡1 mod 3 meaning q is of the form
contradicts our claim that q is also not of the form 3k+1 so we dont have a complete list, infinite
4) (ab/p)= (a/p)(b/p) multiplicativity
Proof
Legendres symbol
Using 3
(ab/p)
Congruent to
(ab)^(p-1)/2
Congruent to
a^(p-1)/2 b^(p-1)/2
Congruent to legendre symbols
(a/p)(b/p)
Mod p
