## Unique Square Sum

#### 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 = 22+32.

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 = a2+b2 = c2+d2.

Clearly HCF(a,b)=1, otherwise a2+b2 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 = c2+d2 = (ka)2+(kb)2 = k2(a2+b2).

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 = a2+b2 = c2+d2, we can write:

a2 = pb2 and d2 = pc2.

a2d2 = (pb2)(pc2) = p2p(b2+c2)+b2c2

a2d2 b2c2 mod p

ad bc mod p

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

As 0 a2, b2, c2, d2 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 p2 = p2+(acbd)2.

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.

Problem ID: 176 (May 2004)     Difficulty: 4 Star

Only Show Problem