CH 7 Quadratic reciprocity Flashcards by Dominique Gabriela

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)

How well did you know this?

Not at all

Perfectly

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

How well did you know this?

Not at all

Perfectly

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

How well did you know this?

Not at all

Perfectly

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

How well did you know this?

Not at all

Perfectly

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.

How well did you know this?

Not at all

Perfectly

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

How well did you know this?

Not at all

Perfectly

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.

How well did you know this?

Not at all

Perfectly

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

How well did you know this?

Not at all

Perfectly

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

How well did you know this?

Not at all

Perfectly

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

How well did you know this?

Not at all

Perfectly

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

How well did you know this?

Not at all

Perfectly

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

How well did you know this?

Not at all

Perfectly

qr mod 7 notation legendres symbol

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

How well did you know this?

Not at all

Perfectly

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

How well did you know this?

Not at all

Perfectly

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

How well did you know this?

Not at all

Perfectly

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

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)

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