CH6 Sums of squares

Question 1

Definition 6.1.1 (Pythagorean triples)

interested in triangles with sides of integer length

Answer 1

Suppose that x, y, z are positive integers satisfying
x² + y² = z².
Then we call
(x, y, z) a Pythagorean triple.

If x, y, z have no common divisor, then we call (x, y, z) a primitive Pythagorean triple.

(interested in positive integers- neagtive versions)

Question 2

e.g are Pythagorean triples?
(3, 4, 5)
(5, 12, 13)
(6, 8, 10)
(15, 36, 39)

Answer 2

(3, 4, 5) and (5, 12, 13) are primitive Pythagorean triples, while (6, 8, 10)
and (15, 36, 39) are non-primitive Pythagorean triples.

Question 3

if d is the greatest
common divisor of the numbers in the Pythagorean triple (x, y, z)

Answer 3

In general, if d is the greatest
common divisor of the numbers in the Pythagorean triple (x, y, z), then (x/d, y/d, z/d)
is a primitive Pythagorean triple.

Question 4

Lemma 6.1.3.
pythogorean triples

Answer 4

If (x, y, z) is a primitive Pythagorean triple, then one of x and y is even
and the other is odd.

PROOF:
Assume both x,y even: 2 is a common divisor of x and y. so 2 | x² and 2|y² and thus gcd is divisible by 2. 2|x²+ y² so 2 | z. This shows that (x, y, z) is not a primitive Pythagorean
triple.

(i look in mod 4 as 2 divides x so 4 divides x²)
Suppose now that x and y are both odd, then x, y ≡ ±1 (mod 4),
so x², y² ≡ 1 (mod 4),
so z² = x² + y² ≡ 2 (mod 4). But this is impossible, as there is no number n so that n² ≡ 2 (mod 4).

Indeed, suppose for the purposes of contradiction that
z² ≡ 2 (mod 4). Then 2 | z², and since 2 is prime, 2 | z, so 4|z², so z² ≡ 0 (mod 4), a contradiction

Question 5

Exercise 6.1.4. Let (x, y, z) be a Pythagorean triple. Show that x ̸= y.

Answer 5

(suppose we have this
z² = 2x²)

by lemma If (x, y, z) is a primitive Pythagorean triple, then one of x and y is even and the other is odd. So we can’t have this.

We do have isosceles right angled triangles but none are primitive pythag triples

If (x, y, z) is primitive, Lemma 6.1.3 says that x and y have different
parity, so of course x ̸= y. If (x, y, z) is not primitive, let d be the greatest common
divisor of x, y, z: then
(x/d , y/d, z/d)
is a primitive Pythagorean triple, hence x/d ̸= y/d, so
x ̸= y.

Question 6

Lemma 6.1.5. If m and n are coprime positive integers and mn is a square then what can we say about m and n?

Answer 6

Lemma 6.1.5. If m and n are coprime positive integers and mn is a square (that is,
mn = a^2 for some a ∈ Z),

then so are each of m and n.

Question 7

PROOF

Lemma 6.1.5. If m and n are coprime positive integers and mn is a square (that is,
mn = a2 for some a ∈ Z), then so are each of m and n.

Answer 7

Proof. If mn is a square, then in its factorisation into prime powers
mn = p₁ᵃ-¹ . . . pᵣᵃ-ʳ
every α_i must be even, say α_i = 2β_i.

By the Fundamental Theorem of Arithmetic, the
prime factorisation of m and n must involve the same primes, and since gcd(m, n) = 1,
each of the primes p_i can only divide one of m and n. Thus the prime factorisation of m is a product of some of the
pᵢᵃ-ᶦ= ( pᵢ ^{βᵢ})^2
and that of n is the product of the others.

Therefore, each of m, n is a product of squares, so is a perfect square. □

Question 8

Theorem 6.1.6 (Primitive Pythagorean triples

Answer 8

Suppose a and b are positive integers, one is odd and one is even, a > b and
gcd(a, b) = 1.

Then
(a² − b², 2ab, a² + b²)

is a primitive Pythagorean triple.

Conversely, if (x, y, z) is a primitive Pythagorean triple, then there exist positive integers a and b satisfying the above conditions, such that (after possibly exchanging x and y if necessary),
(x, y, z) = (a² − b², 2ab, a² + b²)

all primitive pythagorean triples are in this form!

Question 9

PROOF

Suppose a and b are positive integers, one is odd and one is even, a > b and
gcd(a, b) = 1.

Then
(a² − b², 2ab, a² + b²)

is a primitive Pythagorean triple.

Conversely, if (x, y, z) is a primitive Pythagorean triple, then there exist positive integers a and b satisfying the above conditions, such that (after possibly exchanging x and y if necessary),
(x, y, z) = (a² − b², 2ab, a² + b²)

all primitive pythagorean triples are in this form!

Answer 9

FIRSTLY SIMLY check its a pythagorean tripple: (a² − b², 2ab, a² + b²) by squaring etc

CHECK PRIMITIVE: if not primitive then a² − b² and a² + b² are both divisible by a prime p

we have also for + and -:
p|2a² and p| 2b²
p /=2 since a²-b² is odd
(since one of a,b is even the other odd)
thus p|a and p|b, contrary to gcd(a,b)=1 so no such prime, so are primitive.

converse:
Suppose that (x, y, z) is a primitive Pythagorean triple.
By Lemma 6.1.3, one of x and y is odd and one is even, (swap x and y if needed), we may assume that x is odd and y even: y = 2w. Then z is also odd since x² + y² = z².
and each of z ± x is even (and positive). Then
4w² = y² = z² − x²,
(z+x)(z-x)
so
w² =((z − x)/2)((z + x)/2)

The two numbers
(z−x)/2 and (z+x)/2
are coprime, for if some prime p divides each of
(z±x)/2 , then p also divides (z+x)/2 ± (z−x)/2, so p | x and p | z.

Then p divides z² − x² = y², so
p | y. This would contradict the assumption that (x, y, z) is primitive.

Hence we have two numbers which are coprime and positive, and their product is a
square. From Lemma 6.1.5, it follows that they must each be a square too. Let
(z + x)/2= a², and (z − x)/2= b²,
then x = a² − b², z = a² + b² and y = 2w = 2√w² = 2√{a²b²} = 2ab.

Furthermore,
a > b, one of a and b is even and the other is odd, and gcd(a, b) = 1. Thus (x, y, z) =

(a² − b², 2ab, a² + b²)
, as required

Question 10

□
Corollary 6.1.7 (Pythagorean triple

Can be written as

Answer 10

Let a > b and s be positive integers. Then

(s(a² − b²),s(2ab),s(a² + b²))
is a Pythagorean triple.

Conversely, let (x, y, z) be a Pythagorean triple.
Then there exist coprime positive
integers a and b, with a > b, one of them even and the other odd, and such that,
exchanging x and y if necessary, letting

s = gcd(x, y, z) we get

(x, y, z) =
(s(a² − b²),s(2ab),s(a²+b²))

Question 11

PROOF

Let a > b and s be positive integers. Then

(s(a² − b²),s(2ab),s(a² + b²))
is a Pythagorean triple.

Conversely, let (x, y, z) be a Pythagorean triple.
Then there exist coprime positive
integers a and b, with a > b, one of them even and the other odd, and such that,
exchanging x and y if necessary, letting

s = gcd(x, y, z) we get

(x, y, z) =
(s(a² − b²),s(2ab),s(a²+b²))

Answer 11

Proof. It is straightforward to check that
(s(a² − b²),s(2ab),s(a²+b²)) is a Pythagorean triple.

Conversely suppose that (x, y, z) is a Pythagorean triple, and let s be the greatest common divisor of x, y and z. We define
x′ = x/s, y′ = y/s, and z′ = z/s. Then
(x′, y′, z′)
is a Pythagorean triple, and it is primitive since if h > 1 is a common divisor of
x′, y′, z′, then hs > s is a common divisor of x, y, z. We may now apply Theorem 6.1.6,
from which the result follows

proof talked through in lectures only as similar to prev proof

Question 12

if (x,y,z) is oythagorean then using gcd(x,y,z)=d

Answer 12

is a primitive pythagorean
(x/d,y/d,z/d)

Question 13

EXANPLE check triple
(5,12,13)
can be written as prev form mentioned with a and b

Answer 13

checking (15+13)/2 = 18/2=9 = 3^2
(13-5)/2 = 4=2^2

we can write with a=3 and b =2

Question 14

Remark 6.1.8

Answer 14

Note that
x^2 + y^2 = z^2 =⇒
(x/z)² + (y/z)²=1

Therefore, we can use Theorem 6.1.6 to describe all rational solutions to the equation
u² + v² = 1. E.g., (x, y, z) = (3, 4, 5) gives (u, v) =(3/5, 4/5)
with
(3/5)²+ (4/5)²= 1. In
general, if (x, y, z) a primitive Pythagorean triple, then by Theorem 6.1.6 we can find a
and b so that (x, y, z) =
a² − b², 2ab, a² + b²
. Thus
u =x/z=
(a² − b²)/(a² + b²)
v =y/z=2ab/(a²+ b²)

Dividing by a² and denoting t = b/a, we get
u =(1 − t²)/(1 + t²)
v =(2t)/(1 + t²)

Question 15

.
Exercise 6.1.9. Let (x, y, z) be a Pythagorean triple. Show that 60 divides xyz

Answer 15

not discussed?
We observe that 60 = 2^2 · 3 · 5. We will split the proof into three parts, first to show that 3 | xyz, the second to show that 5 | xyz, and finally we will show that 4 | xyz, which will complete the proof.
(1) First we compute the squares modulo 3: 0^2 ≡ 0 (mod 3), 1^2 ≡ 1 (mod 3) and
2^2 ≡ 1 (mod 3). If neither x nor y were divisible by 3, then that would imply that z^2 ≡ 1 + 1 (mod 3), but this is impossible since 2 is not a square modulo 3.
Therefore, 3 | xy (which is in fact a stronger result than saying that 3 | xyz).
(2) Now we compute the squares modulo 5: 0^2 ≡ 0 (mod 5), 1^2 ≡ 1 (mod 5)
and 2^2 ≡ 4 (mod 5), 3^2 ≡ 4 (mod 5) and 4^2 ≡ 1 (mod 5). If 5 did not divide neither x, nor y, nor z, then by looking at the possible cases we obtain that this
would imply that z^2 ≡ 2 (mod 5) or z^2 ≡ 3 (mod 5), but neither 2 nor 3 is a square modulo 5. Therefore, 5 | xyz.

(3) For the final step, we use Corollary 6.1.7, so let a, b, s be positive integers, with
a > b and 2 | ab, such that (x, y, z) = (s(a^2 − b^2), s(2ab), s(a^2 + b^2)). Then
xyz = 2abs^3(a^2 − b^2)(a^2 + b^2).
Since 2 | ab, then 4 | xyz, completing the proof.

Question 16

Exercise 6.1.10. Show that the equation x^2 + y^2 = z^4 has infinitely many solutions in
the positive integers

Answer 16

If I have a sol then (X, Y, Z^2) will be a primitive pythag triple
the condition that the last is a square imposes the new condition
a² − b², 2ab, a² + b²

as we can divide through by gcd(x,y,z) and so we can just assume the gcd =1 so thm 6.1.6 gives the method to produce the primitive Pythagorean triple

the extra condition is that (a,b,z) to be a pythag triple!
which we have infinitely many

Question 17

integer sols of x^2 + y^2 =1

unit circle

Answer 17

if only looking for integer sols they’re going to have to be less than 1?

(1,0)
(0,1)
(-1,0)
(0,-1)

what about rational sols?
rational x=m/n
y= r/s

(m/n)²+ (r/s)²=1
s²m²+n²r²= n²s²

finding a rational sol is the same as finding a pythag triple!
Using our formula we have:(assuming m,n coprimer and s coprime to give primitive pythag triple)

a² − b², 2ab, a² + b²

so we have
m²/n² =
(a² − b²)/(a² + b²)

and i can use to find all rational sols

Question 18

Theorem 6.2.1 (Fermat’s Last Theorem,Wiles 1995)

Answer 18

If n > 2, the equation xⁿ + yⁿ = zⁿ has no solutions among the positive (non-zero) integers.

(later on we look at n=4 and n=prime, as composite can be split up)

Question 19

Pierre de Fermat in 1637, in his copy of Diophantus’ Arithmetica

Answer 19

“It is impossible to separate a cube into two cubes, or a fourth power
into two fourth powers, or in general, any power higher than the
second, into two like powers. I have discovered a truly marvellous
proof of this, which this margin is too narrow to contain.”

In order to prove Fermat’s Last Theorem, it is sufficient to prove the result in the cases
where n = 4 and where n is equal to an odd prime. Indeed, if we can solve xᵃᵇ + yᵃᵇ =zᵃᵇ then we get solutions for n = a and n = b too. Fermat did manage to prove the
first of these cases, which was discovered posthumously, although it does not seem
that he ever publicly announced this.

its sufficient because we can split to (xᵃ)ᵇ+(yᵃ)ᵇ= (zᵃ)ᵇ

Question 20

Theorem 6.2.2 (Fermat)

n=4

Answer 20

The equation
x⁴ + y⁴=z²
has no solutions for integers x, y, z > 0.

In particular,
there is no solution in which z is in addition a square, so Fermat’s Last Theorem holds for n = 4.

Question 21

proof of
x⁴ + y⁴=z² having no sols

Answer 21

method of infinite descent: find the smallest sol in some sense, try to find one even smaller which contradicts the original idea that there was a sol- like the proof that root 2 is irrational!

suppose x⁴ + y⁴=z² holds for some positive integers, among all triples (x,y,z) of positive integers satsifying we choose the minimum possible z. In particular, this means any two of x,y,z are coprime, as if any two have common factor p then we have p | x, p | y, and p²| z, meaning that we can divide through by p⁴,
giving a counterexample with a smaller value of z

(primitive as coprime)
Now (x²,y² ,z) is a primitive Pythag triple so by thm 6.1.6 (swapx,y if req.) we can write x² =a² -b² and y² =2ab z=a² +b²
x is odd so x² ≡ 1 (mod 4).
Hence it follows that a is odd and b is even (the other way around leads to x² ≡ −1, a contradiction)

Let b=2c for c ∈ Z. Then y²=4ac but a and b are coprime meaning a and c also coprime, a and c squares by lemma 6.1.5.
a=v² & c=w²

so x²=a²-4c²=v⁴ -4w⁴=v⁴ giving another primitive pythag triple
(x,2w²,v²)
repeating argument there exists A and B s.t
x=A²-B²
2w²=2AB
v²= A²+B² with A and B corpime and one of them even and one odd
AB=w² so A and B also squares by lemma 6.1.5 say
A=P² & B=Q²
so
P⁴ + Q⁴ = A² + B² = v²
, which means that (P, Q, v) is another solution of the
equation x⁴ + y⁴ = z²
. But we know that v =
√a < a² + b² = z, contradicting the
minimality of z
(called a proof of infinite descent!)

Question 22

We allow the squares to include 0^
, so the first few numbers which can be written as a
sum of two squares are

Answer 22

0, 1, 2, 4, 5, 8, 9, 10, 13, 16, . . . .
Is there a pattern?

Question 23

Exercise 6.3.1 (In exercise sheet). If n ≡ 3 (mod 4), then n is NOT a sum of two
squares.

Answer 23

.

Question 24

Example 6.3.2. We can write 169 as a sum of squares using different numbers of nonzero squares

Answer 24

For example, 169 is already a square, so we can write 169 = 13², but we can also write
169
= 13² (+0^2)
= 5² + 12²
= 12² + 4² + 3²
= 10² + 8² + 2² + 1²
.

could be a question in exam: what kinds of integers are the z in the pythagorean triples?
What integers are sums of two squares?

Question 25

Lemma 6.3.3 (Brahmagupta-Fibonacci identity)

Lemma 6.3.3 is also known as the Diophantus identity, and it dates back at least to the
third century A

Answer 25

For all a, b, c, d ∈ Z we have

(a²+ b²)(c² + d²)
= (ac ± bd)² + (ad ∓ bc)²

Hence, if M and N are the sums of 2 squares, then so is MN

**Proof. **This is immediate on multiplying out both sides. You know it from complex
numbers, as it says that
|a ± ib|²· |c + id|² = |(a ± ib)(c + id)|² □
modulus of complex numbers respect multiplication

lemma says if M,N are integers expressible as a sum of two squares then product MN is also the sum of two squares:
if we want to figure out all integers we can find the primes only, as FTOA says we can express numbers in terms of their prime factorisations

Question 26

Exercise 6.3.4. Prove Brahmagupta’s identity: for every a, b, c, d, n ∈ Z we have

(a² + nb²) (c² + nd²)

= (ac ± nbd)² + (ad ∓ nbc)²

Answer 26

not mentioned

Question 27

Theorem 6.3.5 (Fermat’s two-squares theorem, 1654

Answer 27

Let p be an odd prime. Then p is expressible as the sum of two squares if and only
if p ≡ 1 (mod 4

Question 28

proof

thm fermats two squares
Let p be an odd prime. Then p is expressible as the sum of two squares if and only
if p ≡ 1 (mod 4

Answer 28

First suppose p expressible as sum of two squares, p = n² + m²
(p is prime so p itself is not a square so these must be non zero)

Since p is odd, then p ≡ ±1 (mod 4). On the other hand, the possible values of a square modulo 4 are:
0² ≡ 0 (mod 4),
1² ≡ 1 (mod 4),
2² ≡ 0 (mod 4), and
3² ≡ 1 (mod 4). We observe from this that −1 cannot be obtained by adding up two squares modulo 4, and so p ≡ 1 (mod4)

CONVERSELY
assume p ≡ 1 (mod 4). By Corollary 2.3.3 there exists a z
we can solve z²≡ −1
(mod p), where 1 ≤ z ≤ p − 1.

Hence we have found some multiple of p which is a sum of 2 squares, say np = z² + 1²

as z is at most p-1, p is odd so
np=z²+1 ≤(p-1)²+1 <p²
so 0< n <p.

Let mp be the least positive multiple of p that is the sum of 2 squares mp=x²+y²
suppose for a contradiction m ≥ 2. Also observe that m < p, since clearly
m ≤ n, but from above
np=z²+1 ≤(p-1)²+1 <p²

(we choose the smallest possible multiple)
working in mod m: choose u,v between -m/2 and m/2 s.t u ≡ x and v ≡ y (mod m)

u²+v² ≡x²+y² ≡0 mod m
mr=u²+v²

Now if r = 0 then u = v = 0 meaning that x ≡ 0 ≡ y (mod m), meaning that m | x and m | y.
Thus m²| x² and m²| y²
so m²| (x² + y²) = mp, meaning
that m | p. Since p is prime and 1 < m < p, this is impossible.

so r>0 also
r=(1/m)(u²+v²)
(1/m)((m²/4)+(m²/4)=m/2 <m

By lemma 6.3.3
m²pr=mpmr=(x²+y²)(u²+v²)= (xu+yv)² +(xv-yu)²
Now
xu +yv≡ x²+y²≡0 mod m
xv -yu≡ xy+yx≡0 mod m

Thus each of (xu + yv)² and (xv − yu)² is divisible by m², and so we may divide out by
m², leaving us with
rp = X² + Y² for some X, Y ∈ Z. As 0 < r < m, this contradicts
the minimality of

Question 29

Exercise 6.3.4. Prove Brahmagupta’s identity: for every a, b, c, d, n ∈ Z we have

(a^2 + nb^2) (c^2 + nd^2)
= (ac ± nbd)^2 + (ad ∓ nbc)^2

Answer 29

.

Question 30

.
Theorem 6.3.5 (Fermat’s two-squares theorem, 1

Answer 30

Let p be an odd prime. Then p is expressible as the sum of two squares if and only
if p ≡ 1 (mod 4)

Question 31

proof:
Let p be an odd prime. Then p is expressible as the sum of two squares if and only
if p ≡ 1 (mod 4)

Answer 31

long in notes:

continued:
choose MN between -m/2 and m/2 s.t u≡x mod m
and v≡y mod m
0≡x^2+y^2 ≡u^2+v^2 mod m
thus u^2+v^2=rm
if r=0 u=0,v=0
x≡0 mod m y≡0 mod m
m |x and m|y
m chosen s.t smallest multiple of p for which mp =x^2+y^2
let x=ma and y=mb
mp=m^2a^2+m^2b^2
p=ma^2+mb^2
so m|p
as p is prime either m=1 or m is p we assumed 0<m<p so not possible, so contradiction r acnt be 0 r>0.

rm=u^2 +v^2≤ n^2/4=m^2/2
thus r ≤m/2<m

as p is 1 mod 4 we can use assumptions….
assume m ≤ 2
m^2rp=(mr)(mp)=(u^2+v^2)(x^2+y^2)
=(xu+yv)^2+(xv-yu)^2

last equality from the lemma stating written as sum of 2 squares
each of these squares we know is divisible by m

xu+yv≡u^2+v^2≡0 mod m
xv=yu≡uv-vu=0 mod m
so m^2 |(xu-yv)^2
we can now divide (0) by m^2

rp=(xu+yv)/m)^2+(xv-yu)/m)^2
leads to contradiction of minimality of m
here I have found anither multiple of p that is smaller than m that can be written as sum of two squares

proof is done by contradiction

Question 32

Example 6.3.6. Is p = 41 the sum of two squares?

Answer 32

Since 41 ≡ 1 (mod 4), Theorem 6.3.5 assures us that the answer is yes. Let’s follow the proof through to see how to express
41 as a sum of two squares. We can solve the congruence
**z^2 ≡ −1 (mod 41) **
by taking
z = 9,

since 9^2 = 81 = 2 · 41 − 1. So let’s take m = 2, x = 9, y = 1. Then we work modulo 2 and find u = v = 1, since 9 ≡ 1 (mod 2) and 1 ≡ 1 (mod 2). so choosing u=1 and v=1
r=1
u^2+v^2=2
rp=1 x 41
m^2rp=(2x1)(2x41) now using lemma to write out as sum of two squares

Hence we arrive at
2^2· 1 · 41 =
(9^2 + 1^2)( 1^2 + 1^2)
= (9 · 1 + 1 · 1)^2 + (9 · 1 − 1 · 1)^2 = 10^2 + 8^2

Dividing out by 2^2
leaves us with 41 = 5^2 + 4^2

Question 33

Theorem 6.3.7 (Fermat’s Christmas Theorem, 1640

one of main thms chapter 6

Answer 33

An integer N > 0 is the sum of 2 squares if and only if, when it is factored into a product of powers of distinct primes, each prime of the form 4k + 3 has even exponent

(highest power p^a that divides N satisfies that a is even,
This relates to the prime description of numbers dividing N
e.g if we have a prime that divides N then either that prime is :
is 2,1 mod 4 or 3 mod 4
in the case of 1mod 4 we know sum of 2 squares
3 mod 4 isn’t a sum of 2 squares so we need to ask if it shows up with an even power here)

Question 34

proof

Theorem 6.3.7 (Fermat’s Christmas Theorem, 164

An integer N > 0 is the sum of 2 squares if and only if, when it is factored into
a product of powers of distinct primes, each prime of the form 4k + 3 has even
exponent

Answer 34

we assume is we take n and assume we can write with primes
N=2ⁿ Π_{a}pᵏ-ᵖ Π_{a}p^{2αₚ)

a= p|N s.t p ≡1 mod 4
b= p|N s.t p ≡3 mod 4

The thm is saying N has this form.

But products of sums of squares are themselves sums of squares due to previous
2 is as 2 = 1²+1²

so if these primes are congruent to 1 mod 4: p=x²+y²

now if p^{2αₚ)≡3 mod 4:
as we are imposing even exponent
p^{2αₚ)= (p^{αₚ))² + 0²

now as these are all sums of 2 squares use the lemma to say the product N is

(Proof. We can deal with the prime 2 easily enough by observing that 2 = 1^2 + 1^2. On the other hand, by Theorem 6.3.5, any prime of the form p = 4k + 1 is a sum of two squares. The only other primes are of the form p = 4k + 3, but any even power of p is unproblematic, since p^2n = p^2n + 0. Putting all these together, Lemma 6.3.3 guarantees that any integer of the stated form is the sum of two squares.)

Conversely, suppose that N = x² + y² and that some prime p | N, where p = 4k + 3. ( p ≡3 mod 4)
p|N:
We show that p | x and p | y. Since p is prime, gcd(y, p) = p or gcd(y, p) = 1 as we only had choices 1 or p.
gcd(y, p) = 1 y and p coprime
By Lemma 2.1.8, y has a multiplicative inverse. There is some z ∈ Z where yz ≡ 1 (mod p). So
Nz²= x²z² + y²z²≡ x²z² + 1 (mod p).
But p | N so Nz² ≡ 0 (mod p),
so
x²z² ≡ −1 (mod p)
which contradicts Corollary 2.3.3.
(only primes for which -1 is a square are ones where y mod 4 but here p assumed 3 mod 4- no solution p and y arent coprime)

argument is symmetric in x and y.
Hence p | y and so also p | x.

Thus p² | (x²+y²) =N
Which shows that whenever we have a prime 3 mod 4 that divides sum of 2 squares, the square of the prime also divides
continue repeating this argument
starting with
N/p² =(x/p)²+(y/p)²

If the exact power of p dividing N is odd, we eventually reach a contradiction

N. But we can now repeat the argument,

Question 35

Theorem 6.4.1 (Lagrange, 1770)

main thm ch6

Answer 35

Every N ∈ N is the sum of 4 squares. (As usual, some of these may be 0.)

Question 36

Lemma 6.4.2 (Extra).

Answer 36

(a^2 + b^2 + c^2 + d^2)( A^2 + B^2 + C^2 + D^2)

= (aA + bB + cC + dD)^2 + (aB − bA − cD + dC)^2
+ (aC + bD − cA − dB)^2 + (aD − bC + cB − dA)^2

sums of 4 squares products are also

Thus if M and N are the sums of 4 squares, then so is MN.
Proof. Immediate by multiplying out both side

Question 37

remark extra

Answer 37

Extra. Although the proof of Lemma 6.4.2 is straightforward, you might fairly wonder how anyone came up with it in the first place! Well, as mentioned earlier, the corresponding identity for two squares (Lemma 6.3.3) can be interpreted using complex numbers:
|(a + ib)(c + id)| = |(a + ib)||(c + id)|.

the modulus of product is the product of mods

Similarly Lemma 6.4.2 can be expressed using Hamilton’s quaternions, a system of elements
the form a + ib + jc + kd, where i^2 = j^2 = k^2 = −1, ij = k, jk = i, ki = j, and |a + ib + jc + kd|2 =
a2 + b2 + c^2 + d^2
. (Take care when working with quaternions, since they are not commutative:in general AB ̸= BA)

Question 38

What result do we have when we have prime p congruent to 1 mod 4

p ≡1 mod 4

Answer 38

we found that when
p ≡1 mod 4

we can find a number z s.t
z^2 ≡-1mod p
and so there is a multiple of p which is the sum of 2 squares:
mp=1+z^2

Question 39

Lemma 6.4.3. Suppose p is prime. Then there exists m, where 0 < m < p, such that

Answer 39

Lemma 6.4.3. Suppose p is prime. Then there exists m, where 0 < m < p, such that
mp = x^2 + y^2 + 1

(sum of 3 squares where one is 1)

Question 40

proof of infinite descent!

Answer 40

assume z exists with your properties
show that a smaller k works with properties e.g z/2
z- (1/2)
contradicting the
minimality of z
z cannot exist
(called a proof of infinite descent!)

Question 41

proof:
Lemma 6.4.3. Suppose p is prime. Then there exists m, where 0 < m < p, such that
mp = x^2 + y^2 + 1 for some x,y in Z

Answer 41

We know statement is true for p ≡1 mod 4 (for sum of 2 squares?)
So we show the eq has sol:
case 2 :
2=1+0+1 (x=1, y=0)
we now consider 2 sets:
S_1={ x^2+1 x in {0,…,(p-1)/2}}
S_2={ -(y^2) y in {0,…,(p-1)/2}}
|S_1|=|S_2|= ((p)/2) +1 = (p+1)/2
Pidgeon hole principle: take the number z common to both ( exists z in intersection of S_1 and S_2)
-y^2 = z=1+x^2
meaning
0≡ 1 +x^2+y^2

Proof. We need to solve x2 + y2 ≡ −1 (mod p). Notethatfor p = 2,this is trivial, just take x = 1 and y = 0. Sowewillsuppose p is odd. (Observe that Corollary 2.3.3 establishes the result for p ≡ 1 (mod 4), so we could further assume that p ≡ 3 (mod 4), but in fact we will not need this.

Notwoelements of S1 are congruent mod p, since if 1+ x2 1 ≡ 1+ x2 2, then p | x2 1 − x2 2 so p | (x1 +x2) or (x1 −x2). But since 0 ≤ x1,x2 ≤ p−1 2 bothsituations are impossible, unless x1 = x2. The same holds for S2. Nowboth S1 and S2 have p+1 2 elements. There are at most p possible distinct remainders modulo p, so it must be that some element of S1 (say 1+ x2) is congruent to some element of S2 (say −y2). Thus 1+ x2 +y2 ≡ 0 (mod p), meaning that x2 +y2 +1 = mp for some m. But also 0 ≤ x,y ≤ p−1 2 , andso0 < mp = x2+y2+1 < p2 4 + p2 4 +1 < p2. Thus 0 <m<p. □

Question 42

Exercise 6.4.5. Let r be a positive integer and let x₁ ≥ x₂ ≥ x₃ ≥ x₄ ≥ 0 be such that
2²ʳ⁺¹ = x₁²+x₂²+x₃² + x₄²

Show that x₁ = x₂ = 2ʳ and x₃ = x₄ = 0.

Answer 42

…
skipped?

Question 43

Proof is long so we do a sketch proof:
proving Lagrange
Every N ∈ N is the sum of 4 squares. (As usual, some of these may be 0.)

USING EXAMPLE OF 23

Answer 43

we use the extra part: (a^2 + b^2 + c^2 + d^2)( A^2 + B^2 + C^2 + D^2)

= (aA + bB + cC + dD)^2 + (aB − bA − cD + dC)^2
+ (aC + bD − cA − dB)^2 + (aD − bC + cB − dA)^2

sums of 4 squares products are also and previous lemma:
Suppose p is prime. Then there exists m, where 0 < m < p, such that
mp = x^2 + y^2 + 1 for some x,y in Z

sketch proof: STRATEGY

STEP 1
Apply 6.4.3 to p=(23)
from its proof
S_1={1+0², 1+1², 1+2².,,,.1+11²}
= {1, 2, 5, 10, 17, 26, 37, 50, 65, 82, 101, 122}
≡ {1, 2, 5, 10, 17, 3, 14, 4, 19, 13, 9, 7} mod 23
S_2 = {0, −1, −4, −9, −16, −25, −36, −49, −64, −81, −100, −121}
≡ {0, 22, 19, 14, 7, 21, 10, 20, 5, 11, 15, 17}

distinct numbers between…
intersection: 5=2²+1 and 5 ≡-8²
x=2 y=8
1²+2²≡-8²
8²+ 2²+1²+0²=69=23*3
k=3
we have 23 x 3 as a sum of 3 squares
STEP 2: writing k as the sum of squares
Pick
A=-1≡8 mod 3 (y as small as we can)
B= -1 ≡2 mod 3 (x small again)
C=1≡1
D=0≡0

so A^2+B^2+C^2+D^2 = 3 x 1
is a multiple of 3
small multiple of 3
(taking as small as I can)
by construction
(-1)²+(-1)²+1²+0²=3 1
let l= 1<k =3
STEP 3
Use lemma 6.4.2
(23 x 3)(3 x 1) =
207= 3²23
= (8²+2²+1²+0²)((-1)²+(-1)²+1²+0²}
=(-9²)+(-6²)+9²+3²
=9²+6²+9²+3²
cancel 3²
23=3²+2²+3²+1²

once we have a multiple of 23, smaller cases until we have 1 x 23

Question 44

GENERAL PROOF: Prove if for primes first of legenre

Answer 44

Pick n in N prime

1) 6.4.3 means there exists x,y ,m
s.t
x^2+y^2+1=mn 0<m<n

2) let k>1 be minimum s.t
kn= a^2+b^2+c^2+d^2 for some a,b,c,d

By 1, k≤m<n
3) suppose by contradiction that k>1:
take
A≡a
B≡b
C≡c
D≡d all mod k
as small as poss
s.t|A|,|B,|C|,|D|≤(k)/2
in between -(k-1)/2 and (k)/2

Then A^2+B^2+C^2+D^2 ≡0 mod k
because this sum was a multiple of K and numbers were congruent
and as multiple of k
A^2+B^2+C^2+D^2 = kl
and
A^2+B^2+C^2+D^2 ≤ 4 * ((k/2)^2 =k^2
(as each one at most…)
actually 0< A^2+B^2+C^2+D^2<k^2
because if we had equality all congruent to k/2 )^2
k/2 divides this sum and k^2 divides the other sum… case considered in notes…
otherwise k^2| (a^2+b^2+c^2+d^2) contradiction

So 0< l<k

step 5: use 6.4.3
(kn)(kl)= k^2 x nl
=(a^2+b^2+c^2+d^2)(A^2+B^2+C^2+D^2)
=()^2+()^2+()^2+()^2
k| aA+bB +Cc + dD because of 3
so can divide both sides by k^2
and we have l written as a set of 4 squares, but contradicts minimality of k as we have found a smaller l<k that is the sum of 4 squares. CONTRADICTION

Question 45

e.g can i write 23 as sum of 4 squares

Answer 45

brute force:
1,4,9,16, start with biggest square
23=16+ (7)=16+ 4 +(3) not possible
23= 9+9+4 +1

generalise the strategy for the proof

here p=23 was a prime so we apply the lemma 6.4.3

WE APPLY THIS TO 23 IN THE SKETCH PROOF THIS IS NOT THE NUMBER I WILL GIVE YOU IN THE EXAM

Question 46

Theorem 6.5.1 (Legendre, 1798)

Answer 46

A number N ∈ N is expressible as a sum of 3 squares
if and only if
N is not of the form 4ᵃ(8k + 7).

(these numbers are the only ones that cant be written as sum of 3)

proof omitted only converse proven:

Question 47

examples for

A number N ∈ N is expressible as a sum of 3 squares
if and only if
N is not of the form 4ᵃ(8k + 7).

Answer 47

0=0²+0²+0²
1=1²+0²+0²
2=1²+1²+0
3=1²+1²+1²
4=2²+0²+0²
5=2²+1²+0²
6=2²+1²+1²
7 cannot be
7=2²+1²+1²+1
4ᵃ(8k + 7) a =0 k=0

Question 48

Example 6.5.2. a)
N ≡ 7 (mod 8).

A number N ∈ N is expressible as a sum of 3 squares
if and only if
N is not of the form 4ᵃ(8k + 7).

Answer 48

For this, we first consider the squares modulo 8:
{0, 1, 4}. One can now check easily that no three numbers from {0, 1, 4} (even allowing repetition) can add up to 7 modulo 8.

Question 49

A number N ∈ N is expressible as a sum of 3 squares
if and only if
N is not of the form 4ᵃ(8k + 7).

(these numbers are the only ones that cant be written as sum of 3)

proof omitted only converse proven:
a)

Answer 49

Suppose
N= 4ᵃ(8k + 7)
(descent style proof)

a) say a=0, so N≡ 7 (mod 8)
but x²,y²,z² can only each be
≡ 0,1,4 mod 8

so x²+y²+z² ≡0,1,2,3,4,5,6 but not 7 mod 8

Question 50

step b)
A number N ∈ N is expressible as a sum of 3 squares
if and only if
N is not of the form 4ᵃ(8k + 7).

Answer 50

if a>0
4 | N
N= x²+y²+z² then
x,y,z are even because
x²,y²,z² are ≡0 or 1 mod 4
so x²+y²+z²≡0 mod 4

For this we consider the squares modulo 4:
{0, 1}. One can easily verify that if we pick three elements from {0, 1} (allowing repetition) so that their sum is 0 modulo 4, then the only way this can happen is if
every summand we chose is 0. Thus 4 | x², 4 | y² and 4|z², showing that x, y and z are all even.

Question 51

step c
Suppose 4ᵃ(8k + 7)=N
we will show cannot be expressed as sum of 3 squares

Answer 51

By contradiction:
assume N expressible and its the smallest integer of the form 4ᵃ(8k + 7). which can be written by 3 squares

By part a we conclude a>0
that means 4|N
result in b) if N= x²+y²+z² then
x,y,z are even
thus we can keep dividing by 4 to give another sum of 3 squares
4ᵃ⁻¹(8k + 7) = (N/4)
=(x/2)² +(y/2)² +(z/2)²

contradicts minimality of N
By induction on a N cannot be the sum of three squares

Question 52

Exercise 6.5.3 (In exercise sheet). An integer n ∈ Z is the difference of two squares if and
only if n ̸≡ 2 (mod 4).

Answer 52

sheets

Question 53

Exercise 6.5.4 (In exercise sheet). Let p be a prime of the form p = 4k + 3. Show that
N = p^(2n)
cannot be a sum of two non-zero squares

Answer 53

sheets