mathschallenge.net

Problem

You are given that ALL primes that are one more than a multiple of 4 can be written as the sum of two squares. For example, 13 = 2²+3².

Assuming that a prime is expressible as the sum of two squares, prove that it can be done in only one way.

Solution

Suppose that the prime, p = a²+b² = c²+d².

Clearly HCF(a,b)=1, otherwise a²+b² would be composite; similarly HCF(c,d)=1.

We will begin by establishing a result that will be used later.

If ad = bc then a|bc, but as HCF(a,b)=1, a|c. Let c = ka.

ad = kab d = kb.

So p = c²+d² = (ka)²+(kb)² = k²(a²+b²).

And because of the initial supposition, it is necessary that k = 1. Hence c = ka = a and d = kb = b.

By the symmetry of our initial supposition, from ad = bc we can freely interchange c and d to get ac = bd. And in the same way we can show that c = b and d = a.

Hence our proof will be complete if we can show that either ad = bc or ac = bd.

From the initial supposition, p = a²+b² = c²+d², we can write:

    a² = pb² and d² = pc².

a²d² = (pb²)(pc²) = p²p(b²+c²)+b²c²

a²d² b²c² mod p

ad bc mod p

So either (i) adbc 0 mod p, or (ii) ad+bc 0 mod p.

As 0 a², b², c², d² p

    0 a, b, c, d p

0 ad, bc p

Hence -p adbc p and 0 ad+bc 2p.

If (i) is true then adbc 0 mod p, but as adbc lies between -p and p, it follows that adbc = 0 ad = bc. However, we have shown that if this is true, then c = a and d = b, and the square sum must be unique.

Let now consider (ii), ad+bc 0 mod p. We have shown that ad+bc lies between 0 and 2p, so if this is true then ad+bc = p. This case requires a useful, and tricky, identity to be obtained.

p2	=	(a2+b2)(c2+d2)
	=	a2c2+a2d2+b2c2+b2d2
	=	(ad2+2abcd+b2c2)+(a2c22abcd+b2d2)
	=	(ad+bc)2+(acbd)2

Hence if ad+bc = p, then p² = p²+(acbd)².

This leads to acbd = 0 ac = bd. However, we have shown that if this is true, then c = b and d = a, and once again we show that the square sum is unique.

Hence we prove that p can be written as the sum of two squares in only one way.