Sum of two squares

centered_square_number_13_as_sum_of_two_square_numbers-svg

You can tell whether a number is a sum of two squares by looking at its prime factorisation. It can be written as the sum of two squares unless a prime of form 4n+3 appears in its factorisation with an odd power.

The proofs here use clock arithmetic. I’ve used just = where stricter usage would demand I use ≡, e.g. I write 1+2=0 mod 3, not 1+2≡0 mod 3.

First note that all odd numbers
either = 3 mod 4, i.e. are of form 4n+3, or end in 11 if written in binary, not decimal
or = 1 mod 4, i.e. are of form 4n+1, or end in 01 if written in binary, not decimal.

Claim 1. Every prime number of form 4n+3 cannot be expressed as the sum of two squared whole numbers.

Proof. Every square = 0 or 1 mod 4
Therefore every sum of two squares = 0 or 1 or 2 mod 4 ▇

Claim 2. For every prime number p, the numbers 1, 2, … (p−1) mod p form a group under multiplication. For every element a, ap=a mod p, and ap−1=1 mod p.

Proof. We can prove it is a group just by checking the axioms. In fact it is a cyclic group, but we don’t need that here.

For every a<p, there are ap lists of length p of the numbers 1, 2,… a.

Of those lists, a consist of the same number repeated p times, 1111…1, or 2222…2, etc.

Classify the other lists into “necklaces” by joining the ends. Since each list has length p, and p is prime, i.e. has no divisors other than 1 and p, the list can’t be made up of repeated copies of the same sublist. Therefore two lists make the same “necklace” only if one is the same as the other, only shifted round by r positions, as e.g. 1 2 3 4 5 6 7 makes the same “necklace” as 3 4 5 6 7 1 2.

Therefore p different lists are classified into each “necklace”.

Therefore total number of lists = a + a multiple of p

ap=a mod p ▇

Claim 3. If p is a prime number of form 4n+1, then for some a:

a(p−1)/2=a2n=−1 mod p

Proof. a4n=1 mod p ⇒ a2n=±1

If a2n=1 mod p for every a, then all the elements a are solutions of the equation x2n=1 mod p. But that equation can have at most 2n solutions. Therefore there are only 2n elements in the group 1, 2, … (p−1), which is a contradiction.

So for some a, a(p-1)/2=a2n=−1 mod p ▇

Claim 4. If p is a prime number of form 4n+1, then p can be written as a sum of two squares

Proof. Let i=√(−1) mod p, i.e. an if a2n=−1. Then 1+i2=0 mod p, so 1+i2=a multiple of p, and for every u<p, u2+(iu)2 also=a multiple of p. The job is to prove that we can find a u such that u and iu are small enough.

Let k=⌊√p⌋, i.e. the positive integer k such that k2<p<(k+1)2

Consider the function u+iv for 0≤u≤k and 0≤v≤k

There are (k+1)2 possible values of u+iv

(k+1)2>p

Therefore [by the pigeonhole principle: there are (k+1)2 “pigeons” and only p “holes”] there must be distinct u1, u2, v1, v2, such that:

u1+iv1=u2+iv2 mod p

u1−u2=i(v1−v2) mod p

(u1−u2)2=-(v1−v2)2 mod p

|u1−u2|2+|v1−v2|2=0 mod p [1]

But u≤k and v≤k, so |u1−u2|≤k and |v1−v2|≤k

So |u1−u2|2<p and |v1−v2|2<p

and so [1] ⇒ |u1−u2|2+|v1−v2|2=p ▇

Claim 4: n and m are sums of two squares ⇒ nm is a sum of two squares.

Proof: (a2+b2)(c2+d2)
 =a2c2+b2d2+a2d2+b2c2
 =a2c2+2acbd+b2d2+a2d2−2acbd+b2c2
 =(ac+bd)2+(ad-bc)2 ▇

Since 2 is a sum of squares, it follows that 2n is a sum of squares whenever n is a sum of squares.

Claim 5: If a number n has a prime q of type (4t+3) as a factor not squared (i.e. to an odd power), then n cannot be written as a sum of two squares.

Proof: Suppose a prime q of type (4t+3) does have a multiple (in which q is not squared) which can be written as a sum of two squares. We will derive a contradiction

In other words, we suppose that there is some r, and some x and some y, such that qr=x2+y2, and q is not a factor of x or y.

Take out any factors common to x and y (which must also be squared factors of r). And by reducing mod q, we can without loss of generality have -q/2<x<q/2 and -q/2<y<q/2, so x2+y2<q2 and r<q

By Claim 4 we can without loss of generality have r odd and x and y of opposite parities (one odd, one even)

Then x2+y2 must be of form 4m+1 for some m (it’s of form [2h]2+[2k+1]2 for some h and k)

Since q is of type 4t+3 for some t, r must be of form 4v+3 (for some v) since

qr=x2+y2 mod 4

and right hand side=1 mod 4

Therefore some prime factor w of r must be of form 4u+3 (for some u) (and not squared)

w divides qr, therefore w also has at least one multiple (in which w is not squared), namely qr, which can be written as a sum of two squares

Therefore for every prime q of type (4t+3) which has multiples (in which q is not squared) which can be written as a sum of two squares, there is a smaller prime w of type (4t+3) with the same property

But there is no smaller prime of type (4t+3) than 3.

So neither 3 nor any prime q of type (4t+3) greater than 3 has a multiple including the prime as a not-squared factor such that the multiple can be written as a sum of two squares ▇

Claim 6: For all n, if there are m, a, b such that mn=a2+b2 (and m is not a multiple of n), then n itself can also be written as a sum of whole number squares.

Proof: We can assume n is not a perfect square, otherwise the result is obvious. We can also assume that there is no factor shared by any two of a and b and n [1], otherwise any common factor of two of them must be a factor of the third, and must be a factor of both a and b. Then we can divide both sides of the equation mn=a2+b2 by the common factor squared. (We have thus ruled out such cases as e.g. n=3, m=3, a=3, b=0).

Let t=⌊√n⌋, i.e. the positive integer such that t2<n<(t+1)2

Consider all the numbers au+bv for 0≤u,v≤t

There are (t+1)2 of them, i.e. more than n of them, so two of them must be equal mod n

For some u1,u2,v1,v2

au1+bv1=au2+bv2 mod n

a(u1-u2)=b(v1-v2) mod n

Let x=(u1-u2) and y=(v1-v2), then x<t and y<t and

ax=by mod n

So n divides (ax)2-(by)2 [2]

Since n divides a2+b2, it also divides (ay)2+(by)2 [3]

[2] and [3] ⇒ n divides a2(x2+y2)

But (see [1] above) a and n have no common factors

Therefore n divides (x2+y2)

Since x<t and y<t, x2+y2<2t2<2n

Therefore n=x2+y2

Claim 7. Every number can be written as the sum of two squares unless a prime of form 4n+3 appears in its factorisation with an odd power.

Proof By putting together all the previous claims ▇

See here for a fuller exposition.