# The number of ways of writing an integer as a sum of two squares

Given an integer $m=pq$, where $p,q$ are both primes such that $p\equiv 1 \pmod{4}, q\equiv 1 \pmod{4}$. It is known that $p$ can be written as a sum of two squares (of positive integers) in a unique way, and the same for $q$. Prove that $m$ can be written as a sum of two squares (of positive integers) in exactly two distinct ways.

Attempt

Notice that for positive integers $u,v,A,B$, we have \begin{align*}(u^2+v^2)(A^2+B^2)&=(uA+vB)^2+(vA-uB)^2=(vA+uB)^2+(uA-vB)^2\end{align*} Therefore if $p=a^2+b^2,q=c^2+d^2$, then \begin{align*}m&=(a^2+b^2)(c^2+d^2)=(ac+bd)^2+(bc-ad)^2=(bc+ad)^2+(ac-bd)^2\end{align*} meaning that $m$ can be written as a sum of two squares (of positive integers) in at least two distinct ways.

How do I prove that there doesn't exist a third way of writing $m$ as a sum of two squares (of positive integers)?

• We cannot mark this question as a duplicate since the other question has not (yet) an accepted answer, but this is a duplicate of math.stackexchange.com/questions/1178411/… Mar 8 '15 at 21:08
• Hello, @barto! Are there any other proofs that doesn't involve group theory? Afterall it's an intro number theory exercise. Thanks! Mar 8 '15 at 21:09
• @LiebsterJugendtraum: my answer involves ring theory, more than group theory, but just a little. To this "by hand", you can use Lagrange's identity and try to prove that, assuming that $pq$ has $3$ (or more) distinct representations as a sum of two squares, then $(-1)$ is the square of too many elements in $\mathbb{F}_p^*$ or in $\mathbb{F}_q^*$. Added to my answer. Mar 8 '15 at 21:14

I think we can always translate everything to the basics operations but it will take a huge number of pages! Fortunately, your question has an elementary answer. We denote by $S_n$ the set of representation of the integer $n$ as sum of squares, we have $(a,b)\in S_n$ if and only if $0\leq b<a$ and $a^2+b^2=n$;

Given two primes $p$ and $q$ let: $$S_p=\{(a_p,b_p)\}\\ S_q=\{(a_q,b_q)\}$$ Now we want to prove that $S_{pq}$ contains exactly two elements, or in other words we want to prove that the following equations on unknown $(a,b),(c,d)$ has exactly one solution :

• $a>b>0$ and $c>d> 0$ (it's clear that neither $d=0$ or $b=0$ occurs)
• $a^2+b^2=c^2+d^2=pq$
• $a>c$ ( different elements)

The equation in the middle is equivalent to: $$(a-c)(a+c)=(d-b)(d+b)$$ this implies the existence of integers $x,y,z,t$ pairwise coprime such that: \begin{align} a-c&=&2xy\\ a+c&=&2zt\\d-b&=&2xz\\d+b&=&2yt \end{align} Note that the existence is not hard for example $x=gcd\big(\frac{a-c}{2},\frac{d+b}{2}\big),y=gcd\big(\frac{a-c}{2},\frac{d-b}{2}\big)\cdots$, so this will justify also that they are pairwise corprime.

The result is the fact that: $$pq=(x^2+t^2)(y^2+z^2)$$ obviously $xyzt\neq 0$ therefore $\{p,q\}=\{x^2+t^2,y^2+z^2\}$ we have two cases:

1. $p=x^2+t^2$ and $q=y^2+z^2$, because $a+c>d-b$ we have $t>x$, and $a+c > d+b$ implies $z>y$ so $x=b_p,t=a_p,y=b_q, z=a_q$ so $a=a_pa_q+b_qb_p,b=a_pb_q-b_pa_q,c=a_pa_q-b_qb_p, d=a_pb_q+b_pa_q$
2. $q=x^2+t^2$ and $p=y^2+z^2$ because of the symetry it gives different $x,y,z,t$ but the same $a,b,c,d$ as the first case.

So there is only one solution to the equations hence $S_{pq}$ contains exactly two elements.

• Maybe the best way, is to authorize everything in the presentations (permutations, negative integers) and using the same method you can prove your result but this time without any care about the inequalities. Mar 9 '15 at 0:01
• Thanks a lot, Elaqqad! There is only one part that I don't quite understand. If $p=5,q=13$, then $pq=8^2+1^2=7^2+4^2$, so $(a,b,c,d)=(8,1,7,4)$, and therefore $a+c,a-c,d-b,d+b$ are all odd, so there doesn't exist a tuple of coprime integers $(x,y,z,t)$ which satisfies the system of equations above. I wonder if we can get rid of the coefficient 2 and consider $pq=\frac{1}{4}(x^2+t^2)(y^2+z^2)$. Mar 9 '15 at 3:31
• I think I've got a solution in my reply:) Mar 9 '15 at 5:49

This is strictly related with the number of ways of writing $pq$ as $z\bar{z}$ in $\mathbb{Z}[i]$, that is an Euclidean domain, hence a UFD. See this other question for details.

@LiebsterJugendtraum: my answer involves ring theory, more than group theory, but just a little. To this "by hand", you can use Lagrange's identity and try to prove that, assuming that $pq$ has $3$ (or more) distinct representations as a sum of two squares, then $(-1)$ is the square of too many elements in $\mathbb{F}_p^*$ or in $\mathbb{F}_q^*$.

• Well, this from my introduction to number theory course, which involves only the very basic knowledge of number theory, so I wonder if there are other methods without using UFD. Mar 8 '15 at 21:14
• @LiebsterJugendtraum: Sooner or later, you will have to put some dirt on your hands :) By the way, I sketched a "minimal proof" that does not make use of unique factorization domains, but just semigroups (numbers that are a sum of two squares form a semigroup by Lagrange's identity). Mar 8 '15 at 21:16
• Thanks. I'll think about it :) Mar 8 '15 at 21:19

This is my solution based on your idea and notations. Please point out wherever there is a mistake.

There exist coprime integers $x,y,z,t$ such that

\begin{align*} &a-c=xy\\& a+c=zt\\& d-b=xz\\& d+b=yt \end{align*}

Therefore we have that

\begin{align*} &a=\frac{1}{2}(xy+zt)\\& c=\frac{1}{2}(zt-xy)\\& d=\frac{1}{2}(xz+yt)\\& b=\frac{1}{2}(yt-xz) \end{align*}

Consequently, we obtain that

\begin{align*} &a^2+c^2=\frac{1}{2}(x^2y^2+z^2t^2)\\& b^2+d^2=\frac{1}{2}(x^2z^2+y^2t^2) \end{align*}

which imply that

\begin{align*} &2pq=(a^2+b^2)+(c^2+d^2)=(a^2+c^2)+(b^2+d^2)=\frac{1}{2}(x^2+t^2)(y^2+z^2) \end{align*}

So we have that

\begin{align*}pq=\frac{1}{4}(x^2+t^2)(y^2+z^2)\end{align*}

meaning that there are three possible cases:

\begin{align*} &\{p,q\}=\{\frac{1}{2}(x^2+t^2),\frac{1}{2}(y^2+z^2)\}\\& \{p,q\}=\{\frac{1}{4}(x^2+t^2),(y^2+z^2)\}\\& \{p,q\}=\{(x^2+t^2),\frac{1}{4}(y^2+z^2)\} \end{align*}

Case 1.$\{p,q\}=\{\frac{1}{2}(x^2+t^2),\frac{1}{2}(y^2+z^2)\}$:

If a prime $p_0$ satisfies that $p_0\equiv 1 \pmod 4$, then $p_0=m^2+n^2$ for some positive integers $m,n$ with different parity.

Using $(u^2+v^2)(A^2+B^2)=(uA+vB)^2+(vA-uB)^2=(vA+uB)^2+(uA-vB)^2$, we obtain that $2p_0=(1^2+1^2)(m^2+n^2)=(m+n)^2+(m-n)^2$. The right-hand side is the unique way of writing $2p_0$ as a sum of two squares.

Up to permutation, we may assume that $p=\frac{1}{2}(x^2+t^2),q=\frac{1}{2}(y^2+z^2)$.

If $p=u^2+v^2,q=A^2+B^2$, where $u>v,A>B$,and $u>A)$, then we obtain that

$t>x,z>y$, so $t=u+v,x=u-v,z=A+B,y=A-B$.

\begin{align*} &a=\frac{1}{2}(xy+zt)=uA+vB\\& c=\frac{1}{2}(zt-xy)=vA+uB\\& d=\frac{1}{2}(xz+yt)=uA-vB\\& b=\frac{1}{2}(yt-xz)=vA-uB \end{align*}

Case 2.$\{p,q\}=\{\frac{1}{4}(x^2+t^2),(y^2+z^2)\}$:

If a prime $q_0$ satisfies that $q_0\equiv 1 \pmod 4$, then $q_0=m^2+n^2$ for some positive integers $m,n$ with different parity.

Likewise, we obtain that $4q_0=(0^2+2^2)(m^2+n^2)=(2m)^2+(2n)^2$. The right-hand side is the unique way of writing $4q_0$ as a sum of two squares.

Using the same notations, we have that $t=2u,x=2v,z=A,y=B$, then

\begin{align*} &a=\frac{1}{2}(xy+zt)=vB+uA\\& c=\frac{1}{2}(zt-xy)=uA-vB\\& d=\frac{1}{2}(xz+yt)=vA+uB\\& b=\frac{1}{2}(yt-xz)=uB-vA \end{align*}

Case 3.$\{p,q\}=\{\frac{1}{4}(x^2+t^2),(y^2+z^2)\}$:

This is analogous to case 2.

Consequently, we know that $\{(a,b),(c,d)\}=\{(uA+vB,vA-uB),(vA+uB,uA-vB)\}$, so the product of two distinct primes can be written as a sum of two squares in exactly two ways. $\blacksquare$