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$² = $p$$b$² and $d$² = $p$$c$².

$a$²$d$² = ($p$$b$²)($p$$c$²) = $p$²$p$($b$²+$c$²)+$b$²$c$²

$a$²$d$² $b$²$c$² mod $p$

$ad$ $bc$ mod $p$

So either (i) $ad$$bc$ 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$ $ad$$bc$ $p$ and 0 $ad$+$bc$ 2$p$.

If (i) is true then $ad$$bc$ 0 mod $p$, but as $ad$$bc$ lies between -$p$ and $p$, it follows that $ad$$bc$ = 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 2$p$, so if this is true then $ad$+$bc$ = $p$. This case requires a useful, and tricky, identity to be obtained.

$p$2	=	($a$2+$b$2)($c$2+$d$2)
	=	$a$2$c$2+$a$2$d$2+$b$2$c$2+$b$2$d$2
	=	($ad2$+2$abcd$+$b$2$c$2)+($a$2$c$22$abcd$+$b$2$d$2)
	=	($ad$+$bc$)2+($ac$$bd$)2

Hence if $ad$+$bc$ = $p$, then $p$² = $p$²+($ac$$bd$)².

This leads to $ac$$bd$ = 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.