Sums of Two Squares

Expanding gives $(ac-bd{)}^2+(ad+bc{)}^2=a^2{c}^2-2abcd+b^2{d}^2+a^2{d}^2+2abcd+b^2{c}^2=(a^2+b^2)(c^2+d^2)$.

Likewise $(ac+bd{)}^2+(ad-bc{)}^2=a^2{c}^2+2abcd+b^2{d}^2+a^2{d}^2-2abcd+b^2{c}^2=(a^2+b^2)(c^2+d^2)$.

Choose integers $a,b,c,d$ with $m=a^2+b^2$ and $n=c^2+d^2$.

Then $mn=(ac-bd{)}^2+(ad+bc{)}^2$ by the two-square identity.

The displayed integer pair represents $mn$ by [F1]. This also covers a zero factor, for which the pair $(0,0)$ represents zero and the same formula gives the zero product.

If $x^2+y^2=m$, oddness of $m$ makes $x,y$ have opposite parity, so $x+y$ and $x-y$ are odd; moreover $(x+y{)}^2+(x-y{)}^2=2m$, so $\mathrm{\Phi }$ sends representations of $m$ to representations of $2m$.

If $u^2+v^2=2m$, reduction modulo $4$ shows that $u$ and $v$ are both odd: their squares cannot both be even because $2m\equiv 2(\mathrm{m}\mathrm{o}\mathrm{d}4)$, and they cannot have opposite parity because their square sum would be odd. Thus $\mathrm{\Psi }(u,v)$ has integer coordinates, and their squared sum is $(u^2+v^2)\mathrm{/}2=m$.

Direct substitution gives $\mathrm{\Psi }(\mathrm{\Phi }(x,y))=(x,y)$ and $\mathrm{\Phi }(\mathrm{\Psi }(u,v))=(u,v)$.

Suppose $(x,y)$ is primitive and a common divisor greater than $1$ divides both coordinates of $\mathrm{\Phi }(x,y)$. By [L1] it has a prime divisor $\mathrm{\ell }$. Since $x+y$ and $x-y$ are odd, $\mathrm{\ell }$ is odd; because $\mathrm{\ell }$ divides $2x$ and $2y$, [L2] gives $\mathrm{\ell }\mid x$ and $\mathrm{\ell }\mid y$, contradicting primitivity. Hence $\mathrm{\Phi }(x,y)$ is primitive.

Suppose $(u,v)$ is primitive and a common divisor greater than $1$ divides both coordinates of $\mathrm{\Psi }(u,v)$. A prime divisor $\mathrm{\ell }$ supplied by [L1] then divides their sum $u$ and difference $v$, contradicting primitivity. Hence $\mathrm{\Psi }(u,v)$ is primitive.

The mutually inverse maps of step 2.1 give the first bijection, and steps 2.2 and 2.3 show that they restrict to mutually inverse maps on primitive representations.

The divisibility hypothesis is the congruence $x^2+y^2\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}q)$.

If $q\mid y$, then step 1.1 gives $q\mid x^2$, so [L3] gives $q\mid x$; the same argument with the coordinates interchanged handles $q\mid x$.

If neither coordinate were divisible by $q$, the nonzero class of $y$ would be invertible in the field $\mathbb{Z}\mathrm{/}q$, and step 1.1 would give $(x{y}^{-1}{)}^2=-1$. Thus $-1$ would be a nonzero quadratic residue and $(-1\mathrm{/}q)=1$.

Since $q\equiv 3(\mathrm{m}\mathrm{o}\mathrm{d}4)$, [L1] instead gives $(-1\mathrm{/}q)=-1$, contradicting step 2.2.

Hence at least one coordinate is divisible by $q$, and step 2.1 makes both divisible by $q$. Writing $x=q{x}_0$ and $y=q{y}_0$ gives $x^2+y^2=q^2(x_0^2+y_0^2)$.

Let $Q$ be the set of all square classes in $\mathbb{Z}\mathrm{/}p$, including zero. By [L1], $\mathrm{\mid }Q\mathrm{\mid }=(p+1)\mathrm{/}2$.

Translation and negation are bijections of the additive group, so $a-Q:=\{a-z:z\in Q\}$ also has $(p+1)\mathrm{/}2$ elements.

Suppose, for contradiction, that $Q$ and $a-Q$ are disjoint. Then [L3] gives $\mathrm{\mid }Q\cup (a-Q)\mathrm{\mid }=(p+1)\mathrm{/}2+(p+1)\mathrm{/}2=p+1$.

But $Q\cup (a-Q)\subseteq \mathbb{Z}\mathrm{/}p$, so [L2] and [L4] give $\mathrm{\mid }Q\cup (a-Q)\mathrm{\mid }\le p$, contradicting step 3.1.

Choose $z\in Q\cap (a-Q)$. Write $z=[x^2]$ and $z=[a-y^2]$ for integers $x,y$. Then $[x^2+y^2]=[a]$ by [L5], which is the required congruence.

The set $H:=\{k\in \mathbb{N}:k\le p\text{ and }{k}^2<p\}$ is finite and contains $0$, so [L1] gives its largest element $h$.

One has $(h+1{)}^2>p$: a strict inequality in the other direction would put $h+1$ in $H$, while equality would factor the prime $p$ as $(h+1)(h+1)$ with $1<h+1<p$. Also $h^2<p=(\sqrt{p}{)}^2$, so $h<\sqrt{p}$ by nonnegativity and [L2].

Put $I:=\{0,1,\dots ,h\}$. Then [L3] gives $\mathrm{\mid }I\times I\mathrm{\mid }=(h+1{)}^2>p=\mathrm{\mid }\mathbb{Z}\mathrm{/}p\mathrm{\mid }$ by step 2.1 and [L4].

Apply [L5] to $(i,j)\mapsto [ia-j{]}_p$. Distinct pairs $(i,j),(i^{\mathrm{\prime }},j^{\mathrm{\prime }})\in I\times I$ have the same image. With $r=i-i^{\mathrm{\prime }}$ and $s=j-j^{\mathrm{\prime }}$, this says $ra\equiv s(\mathrm{m}\mathrm{o}\mathrm{d}p)$.

The coordinate bounds give $\mathrm{\mid }r\mathrm{\mid },\mathrm{\mid }s\mathrm{\mid }\le h<\sqrt{p}$.

If $r=0$, then [F1] gives $p\mid s$; the bound $\mathrm{\mid }s\mathrm{\mid }<\sqrt{p}<p$ forces $s=0$, contrary to distinctness. If $s=0$, then $p\mid ra$; [L6] and $p\nmid a$ give $p\mid r$, and the same bound forces $r=0$, again a contradiction.

Thus the integers $r,s$ from step 4.1 are both nonzero, satisfy $ra\equiv s(\mathrm{m}\mathrm{o}\mathrm{d}p)$, and obey the required strict bounds.

If an odd prime satisfies $p=x^2+y^2$, the square residues modulo $4$ show that $x,y$ have opposite parity and hence $p\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}4)$.

The remaining even prime has the representation $2=1^2+1^2$.

For the converse direction, suppose $p\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}4)$. Then $p$ is odd, and [L2] and [F2] provide an integer $a$ with $a^2\equiv -1(\mathrm{m}\mathrm{o}\mathrm{d}p)$ and $p\nmid a$.

Apply [L1] to this $a$ to obtain nonzero integers $r,s$ with $\mathrm{\mid }r\mathrm{\mid },\mathrm{\mid }s\mathrm{\mid }<\sqrt{p}$ and $ra\equiv s(\mathrm{m}\mathrm{o}\mathrm{d}p)$.

Squaring the congruence in step 2.1 and using $a^2\equiv -1$ gives $p\mid r^2+s^2$. Moreover $0<r^2+s^2<p+p=2p$. The only positive multiple of $p$ below $2p$ is $p$, so $p=r^2+s^2$.

Step 1.1 proves necessity for odd primes, step 1.2 handles $p=2$, and step 3.1 proves sufficiency when $p\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}4)$.

Since $u^2-x^2=y^2-v^2>0$, one has $0<v<y$, and $(u-x)(u+x)=(y-v)(y+v)$. All four factors are positive and even, so with $A=(u+x)\mathrm{/}2$, $B=(u-x)\mathrm{/}2$, $C=(y+v)\mathrm{/}2$, and $D=(y-v)\mathrm{/}2$ one has $AB=CD$.

Let $g=\gcd (A,C)$ and write $A=eg$, $C=fg$. Positivity gives $e,f,g>0$, and $\gcd (e,f)=1$, since a common divisor greater than one would make a common divisor of $A,C$ larger than $g$.

The equality $AB=CD$ becomes $eB=fD$. Since $\gcd (e,f)=1$, [L2] gives $e\mid D$ and $f\mid B$; write $D=eh$ and $B=fh$ with $h>0$.

From $A=eg$, $B=fh$, $C=fg$, and $D=eh$ one obtains $u=A+B=eg+fh$, $x=A-B=eg-fh$, $y=C+D=fg+eh$, and $v=C-D=fg-eh$.

By [L1], $(e^2+f^2)(g^2+h^2)=(eg+fh{)}^2+(fg-eh{)}^2=u^2+v^2=N$. Each factor exceeds one because all four entries are positive.

By [L1], choose integers $a,b$ with $p=a^2+b^2$.

Neither coordinate is zero, since a prime cannot be a square of an integer greater than one. Since $p$ is odd, exactly one coordinate is odd: two odd squares sum to $2$ modulo $4$, and two even squares give an even sum. Changing signs and interchanging coordinates therefore turns every representation into a positive normalized one.

If two normalized representations differed, their positive odd coordinates would differ; order them as $0<x<u$ and apply [L2]. This would write the prime $p$ as a product of two integers greater than one, a contradiction. Hence the normalized representation is unique.

Step 1.1 supplies the normalized pair, step 2.1 makes it unique, and undoing the sign changes and interchange in step 1.2 gives all ordered signed representations and no others.

For every prime $\mathrm{\ell }$, the exponent-zero power is ${\mathrm{\ell }}^0=1=1^2+0^2$.

If $q\equiv 3(\mathrm{m}\mathrm{o}\mathrm{d}4)$, every even power has the explicit representation $q^{2j}=(q^j{)}^2+0^2$.

If $q^{2j+1}=x^2+y^2$, then [L2] gives $x=q{x}_1$ and $y=q{y}_1$, so $q^{2j-1}=x_1^2+y_1^2$ when $j\ge 1$; at $j=0$, the same divisibility would make $q^2$ divide $q$, which is impossible. Induction on $j$ repeatedly reduces any alleged odd-exponent representation to that impossible base case.

The prime $2$ and every prime $p\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}4)$ are represented by [L3]. Multiplying an induction-stage representation by the prime representation and using [L1] gives one for the next power, so [L4] represents all their natural powers.

Steps 1.1 and 2.1 handle $2$ and primes congruent to one modulo four, while steps 1.2 and 1.3 prove both directions for primes congruent to three modulo four.

For the reverse direction at $n=1$, the canonical factorisation is empty and $(1,0)$ represents $1$.

For the reverse direction at $n>1$, assume every three-mod-four prime has even valuation. By [L3], every prime-power factor in [L4] is representable.

For the forward direction, suppose $n=x^2+y^2$ and let $q\equiv 3(\mathrm{m}\mathrm{o}\mathrm{d}4)$ divide $n$. By [L2], $x=q{x}_1$ and $y=q{y}_1$, so $n=q^2{n}_1$ with $n_1=x_1^2+y_1^2$.

Repeatedly applying [L1] to the finite list of factors from step 1.2 gives a representation of their product $n$; step 1.1 supplies the empty-list case.

By [L5] and [L6], step 1.3 lowers the $q$-adic valuation by exactly two: $v_q(n_1)=v_q(n)-2$.

If $v_q(n)$ were odd, induction on the number of two-step reductions in steps 1.3 and 2.2 would eventually give a represented integer of $q$-valuation one. Applying step 1.3 once more would make its valuation at least two, a contradiction. Thus $v_q(n)$ is even.

Steps 2.1 and 3.1 prove the reverse and forward directions, respectively.

Put $X=ac-bd$ and $Y=ad+bc$. By [L1], $X^2+Y^2=PQ$.

Suppose, for contradiction, that $(X,Y)$ is not primitive. Its positive gcd then exceeds one, so choose by [L2] a prime $\mathrm{\ell }$ dividing both $X$ and $Y$.

The combinations $aX+bY=cP$ and $aY-bX=dP$ are divisible by $\mathrm{\ell }$. Since $(c,d)$ is primitive, $\mathrm{\ell }$ cannot divide both; applying [L3] to the combination with coefficient not divisible by $\mathrm{\ell }$ gives $\mathrm{\ell }\mid P$.

Similarly, $cX+dY=aQ$ and $cY-dX=bQ$. Primitivity of $(a,b)$ and [L3] give $\mathrm{\ell }\mid Q$.

Steps 2.1 and 2.2 contradict $\gcd (P,Q)=1$. Hence $(X,Y)$ is primitive and, by step 1.1, primitively represents $PQ$.