CH 7 Quadratic reciprocity

Question 1

We have learned how to solve linear congruences:

for instance, 2x ≡ 3 (mod 13).

Answer 1

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)

Question 2

n quadratic equations: can we find a solution of x^2 ≡ 2 (mod 13)?

Answer 2

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

Question 3

def 7.1.2
quadratic residue

Answer 3

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

Question 4

example:lecture only
quadratic residues mod 3
mod 5
mod 7

Answer 4

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

Question 5

skipped then done
Example 7.1.1. We want to find x such that
2x^2 + x + 1 ≡ 0 (mod 13).

Answer 5

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.

Question 6

skipped
Example 7.1.3. Let us compute all possible squares modulo 13 (beyond 0, which is
obviously a quadratic residue):

Answer 6

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

Question 7

PROPn
7.1.4
how many quadratic residues?

Answer 7

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.

Question 8

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.

Answer 8

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

Question 9

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

Answer 9

sheet

Question 10

Definition 7.2.1 (The Legendre symbol)

Answer 10

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

Question 11

e.g _ is a primitive root mod 7

Answer 11

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

Question 12

Example 7.2.2. Repeating Example 7.1.3, we have

Answer 12

(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

Question 13

qr mod 7 notation legendres symbol

Answer 13

(1/7) = (4/7) =1
(3/7)=-1 etc not QR

Question 14

Lemma 7.2.3 for legendres symbols

Answer 14

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

Question 15

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

Answer 15

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

Question 16

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

Answer 16

Idea is that sols are given by a formula, knowing which numbers are squares mod n will help here….

exercise?

Question 17

where does law of reciprocity come from

Answer 17

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

Question 18

Theorem 7.3.1 (Gauss’ law of reciprocity, art. 151)

Answer 18

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)

Question 19

Theorem 7.3.2 (Supplementary laws)

to Gauss’ law of reciprocity

Answer 19

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.

Question 20

Example 7.3.3

legendre symbol
compute
(2/23/)

Answer 20

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

Question 21

legendre symbol
compute
(2223/3779)

Answer 21

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.

Question 22

Exercise 7.3.5. Compute (12703/16361) (both numbers are prime).

Answer 22

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.

Question 23

Lemma 7.3.6 (Gauss’ lemma, 1808).

Legendre symbol for a/p

With odd prime and a an integer comprime

Answer 23

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

Question 24

Example of gauss’ lemma

7.3.7
a = 5, p = 13.
q: is 5 a QR mod 13?

Answer 24

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:

Question 25

q: is 5 a QR mod 13?
quadratic reciprocity answer:

Answer 25

(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

Question 26

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

Answer 26

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…

Question 27

SUMMARY CH7
main tools

Answer 27

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

Question 28

Proof of the Supplementary laws.

Answer 28

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

Question 29

Proposition 7.4.1. If q = 2n + 1 is an odd prime and q ≡ ±1 (mod 8), then

Answer 29

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.

Question 30

M_11 = 2^11 − 1 prime? mersenne prime?

Answer 30

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

Question 31

Proposition 7.4.2. primes of the form 8k + 7?

Answer 31

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

Question 32

Proposition 7.4.3. primes of the form 3k + 1.

Answer 32

Proposition 7.4.3. There are infinitely many primes of the form 3k + 1.

Question 33

Proposition 7.4.3. There are infinitely many primes of the form 3k + 7.
PROOF

Answer 33

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

Question 34

4) (ab/p)= (a/p)(b/p) multiplicativity

Proof
Legendres symbol

Answer 34

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