p is prime. Show that there is at most one $(m,n) \in \mathbb Z^2$ with $0<m\le n$ that solves $p = m^2 + n^2$

Question

I've been trying to solve this question without great success. I've found that the problem is correct for $p \equiv 1 \mod 4$.

Thank you,

Answer 1

Let $p=2$, then $p=1^2+1^2$. So assume $p$ is an odd prime s.t. $p=a^2+b^2$, hence neither $a$ nor $b=0$. Now $a$ has a multiplicative inverse $c$ modulo $p$: $ac\equiv1\pmod{p}$.

$$(ac)^2+(bc)^2\equiv1+(bc)^2\equiv0\pmod{p}\implies (bc)^2\equiv-1\pmod{p}$$ and so $-1$ is a quadratic residue modulo $p$. Let $bc\equiv d$ then $$d^2+1\equiv0\pmod{p}\tag{1}$$ Now $\gcd(d,p)=1$ so there exists a unique solution to the congruence $$dx\equiv y\pmod{p}\tag{2}$$ where $0<|x|<\sqrt{p}$ and $0<|y|<\sqrt{p}$. To see this let $m=\lfloor\sqrt{p}\rfloor$, and consider the $(m+1)^2$ numbers $jd+k$, where $1\le j,k\le m+1$. Since $(m+1)^2>p$, at least two of the numbers are in the same residue class, say $$x_1d+y_1\equiv x_2d+y_2\pmod{p}\implies (x_1-x_2)d\equiv (y_2-y_1)\pmod{p}$$ where $x_1\neq x_2$ or $y_1\neq y_2$. Since if one of the terms is zero, so is the other, then neither is, and we have $x=x_1-x_2$, $y=y_2-y_1$.

Multiply $(1)$ by $x^2$ and use $(2)$ to give $$(d^2+1)x^2=(dx)^2+x^2\equiv y^2+x^2\equiv0\pmod{p}\tag{3}$$ Now $0<x^2+y^2<2p$, implying $x^2+y^2=p$.

To discover which primes can be written as the sums of two squares we have that if $\gcd(a,p)=1$ then Euler's criterion gives $$(-a|p)\equiv(-a)^{(p-1)/2}\equiv(-1)^{(p-1)/2}a^{(p-1)/2}\equiv(-1)^{(p-1)/2}(a|p)\pmod{p}$$ from which $(-a|p)=(-1)^{(p-1)/2}(a|p)$ (here $(a|p)$ is the Legendre symbol). This gives the results:

If $p=4n+1$, $(p-1)/2$ is even, so $$(-a|p)= (a|p)$$ If $p=4n+3$, $(p-1)/2$ is odd, so $$(-a|p)=-(a|p)$$ This shows an odd prime $p$ can be written as the sum of two squares if and only if it is of the form $4n+1$ (for then $(-1|p)=(1|p)=1$, and we need $-1$ a quadratic residue modulo $p$).

We now show these are the only numbers that can be represented in this way. By the Brahmagupta-Fibonacci Identity has it that if two numbers can be written as the sum of two squares then so can their product: $$(a^2+b^2)(d^2+c^2)=(ad+bc)^2+(ac-bd)^2$$ Now if $N=m^2k$ where $k$ is square free, then $N$ can be written as the sum of two squares if and only if $k$ contains no factors of the form $4n+3$. If $k$ has no such factors we can write $k=f^2+g^2$, and so $m^2k=(mf)^2+(mg)^2$ is the sum of two squares.

Conversely if $N=a^2+b^2=m^2k$, and $\gcd(a,b)=d$ then $d^2\mid m^2$. Let $a=a_1d$, $b=b_1d$. Then $$a_1^2+b_1^2\equiv0\pmod{k}\tag{4}$$ Now $\gcd(a_1,b_1)=1$, so if an odd prime $p\mid k$ then one of $a_1$, $b_1$ is prime to $k$. Say $\gcd(a_1,k)=1$. Then there exists a multiplicative inverse $c$ s.t. $$ca_1\equiv1\pmod{p}$$ and so by $(4)$ $$(a_1c)^2+(b_1c)^2\equiv1+(b_1c)^2\equiv0\pmod{p}\implies (b_1c)^2\equiv-1\pmod{p}$$ implying $-1$ is a quadratic residue modulo $p$. Hence $p$ is of the form $4n+1$.

Answer 2

It is easy to see $m$ or $n$ is odd and the other is even. So let $m=2x-1$ and $n=2y$. $p=m^2+n^2=4x^2-4x+1+4y^2=4(x^2-x+y^2)+1$. Hence $p$ has to be of the form $4\ell+1$.

Let $x=m+in \in \mathbb{Z[i]}$. Let $N(x)$ be the norm of $x$.

Since $N(x)= m^2+n^2=p$ a prime, Hence $x$ is a prime in $\mathbb{Z[i]}$.

Now suppose $m_1^2+n_1^2=m_2^2+n_2^2$ then

$(m_1+in_1)(m_1-in_1)=(m_2+in_2)(m_2-in_2)$.

Since $m_1+in_1$ is a prime :$(m_1+in_1)$ divides $(m_2+in_2)$ or $(m_2-in_2)$.

Let $(m_1+in_1)$ divide $(m_2+in_2)$ and since primes are irreducible in $\mathbb{Z[i]}$:

$u(m_1+in_1)=(m_2+in_2)$

where $u$ is a unit in $\mathbb{Z[i]}$ and units in $\mathbb{Z[i]}$ are just $1,-1,i,-i$.

Hence proved.