CH6 Sums of squares Flashcards
Definition 6.1.1 (Pythagorean triples)
interested in triangles with sides of integer length
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)
e.g are Pythagorean triples?
(3, 4, 5)
(5, 12, 13)
(6, 8, 10)
(15, 36, 39)
(3, 4, 5) and (5, 12, 13) are primitive Pythagorean triples, while (6, 8, 10)
and (15, 36, 39) are non-primitive Pythagorean triples.
if d is the greatest
common divisor of the numbers in the Pythagorean triple (x, y, z)
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.
Lemma 6.1.3.
pythogorean triples
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
Exercise 6.1.4. Let (x, y, z) be a Pythagorean triple. Show that x ̸= y.
(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.
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?
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.
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.
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. □
Theorem 6.1.6 (Primitive Pythagorean triples
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!
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!
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
□
Corollary 6.1.7 (Pythagorean triple
Can be written as
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²))
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²))
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
if (x,y,z) is oythagorean then using gcd(x,y,z)=d
is a primitive pythagorean
(x/d,y/d,z/d)
EXANPLE check triple
(5,12,13)
can be written as prev form mentioned with a and b
checking (15+13)/2 = 18/2=9 = 3^2
(13-5)/2 = 4=2^2
we can write with a=3 and b =2
Remark 6.1.8
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²)
.
Exercise 6.1.9. Let (x, y, z) be a Pythagorean triple. Show that 60 divides xyz
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.
Exercise 6.1.10. Show that the equation x^2 + y^2 = z^4 has infinitely many solutions in
the positive integers
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
integer sols of x^2 + y^2 =1
unit circle
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
Theorem 6.2.1 (Fermat’s Last Theorem,Wiles 1995)
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)
Pierre de Fermat in 1637, in his copy of Diophantus’ Arithmetica
“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ᵃ)ᵇ
Theorem 6.2.2 (Fermat)
n=4
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.
proof of
x⁴ + y⁴=z² having no sols
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!)
We allow the squares to include 0^
, so the first few numbers which can be written as a
sum of two squares are
0, 1, 2, 4, 5, 8, 9, 10, 13, 16, . . . .
Is there a pattern?
Exercise 6.3.1 (In exercise sheet). If n ≡ 3 (mod 4), then n is NOT a sum of two
squares.
.
Example 6.3.2. We can write 169 as a sum of squares using different numbers of nonzero squares
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?
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
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
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)²
not mentioned
Theorem 6.3.5 (Fermat’s two-squares theorem, 1654
Let p be an odd prime. Then p is expressible as the sum of two squares if and only
if p ≡ 1 (mod 4
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
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
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
.
.
Theorem 6.3.5 (Fermat’s two-squares theorem, 1
Let p be an odd prime. Then p is expressible as the sum of two squares if and only
if p ≡ 1 (mod 4)
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)
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
Example 6.3.6. Is p = 41 the sum of two squares?
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
Theorem 6.3.7 (Fermat’s Christmas Theorem, 1640
one of main thms chapter 6
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)
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
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,
Theorem 6.4.1 (Lagrange, 1770)
main thm ch6
Every N ∈ N is the sum of 4 squares. (As usual, some of these may be 0.)
Lemma 6.4.2 (Extra).
(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
remark extra
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)
What result do we have when we have prime p congruent to 1 mod 4
p ≡1 mod 4
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
Lemma 6.4.3. Suppose p is prime. Then there exists m, where 0 < m < p, such that
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)
proof of infinite descent!
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!)
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
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. □
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.
…
skipped?
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
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
GENERAL PROOF: Prove if for primes first of legenre
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
e.g can i write 23 as sum of 4 squares
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
Theorem 6.5.1 (Legendre, 1798)
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:
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).
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
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).
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.
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)
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
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).
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.
step c
Suppose 4ᵃ(8k + 7)=N
we will show cannot be expressed as sum of 3 squares
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
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).
sheets
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
sheets
