Prove that $a^2+b^2=p$ has a unique solution $(a,b)\in\mathbb{Z}_{\ge0}^2$ with $a\le b$, where $p\equiv 1\pmod4$ is prime.

Question

I am trying to prove the following:

Consider $p$, a prime natural number with $p\equiv 1\pmod4$. Show that the equation $a^2 + b^2 = p$ has a unique solution $a, b \in \mathbb{Z}_{≥0}$, up to swapping $a$ and $b$.

I know if $p\equiv 1(\bmod4)$ then $p = (a + bi)(a − bi)$ is a prime factorisation, which I think gets me part of the way there, but I don't know how to prove it.

Answer 1

If we have two ways to write $p$ as a sum of two squares: $$ p=a^2+b^2=c^2+d^2 $$ then that would give rise to two prime factorizations $$ p=(a+bi)(a-bi)=(c+di)(c-di) $$ But the fundamental theorem of arithmetic is still valid in the Gaussian integers. So these two factorizations must be the same, up to order, and factors of $i$. Thus $a^2,b^2$ must be the same two squares as $c^2,d^2$ (albeit possibly not in the same order).

Answer 2

The uniqueness part follows from the identity $$a^2c^2-b^2d^2=(a^2+b^2)c^2-b^2(c^2+d^2)\,.$$ Thus, if $a^2+b^2=p$ and $c^2+d^2=p$, then $a^2c^2\equiv b^2d^2\pmod{p}$, or $ac\equiv \pm bd\pmod{p}$.

If $ac\equiv +bd\pmod{p}$, then note that $$p^2=(a^2+b^2)(c^2+d^2)=(ac-bd)^2+(ad+bc)^2\,.$$ Show that this means $ac=bd$, and so $(a,b)=(d,c)$. If $ac\equiv -bd\pmod{p}$, then note that $$p^2=(a^2+b^2)(c^2+d^2)=(ac+bd)^2+(ad-bc)^2\,.$$ Show that this means $ad=bc$, and so $(a,b)=(c,d)$.

The existence part is done by first observing that $x^2\equiv -1\pmod{p}$ has a solution $x\in\mathbb{Z}$. Now, consider the set $$S:=\big\{0,1,2,\ldots,\lfloor\sqrt{p}\rfloor\big\}\times\big\{0,1,2,\ldots,\lfloor\sqrt{p}\rfloor\big\}\,.$$ Note that $$|S|=\big(\lfloor\sqrt{p}\rfloor+1\big)^2>\big(\sqrt{p}\big)^2=p\,.$$ Ergo, by the Pigeonhole Principle, there are two distinct pairs $(a_1,b_1)$ and $(a_2,b_2)$ in $S$ such that $$a_1x-b_1\equiv a_2x-b_2\pmod{p}\,.$$ Let $a:=|a_1-a_2|$ and $b:=|b_1-b_2|$. We have that $$a^2+b^2= (a_1-a_2)^2+(b_1-b_2)^2\equiv (b_1-b_2)^2\left(x^2+1\right)\equiv 0\pmod{p},$$ and $0\leq a,b\leq \lfloor\sqrt{p}\rfloor<\sqrt{p}$. Since $a$ and $b$ cannot be both zero (otherwise $(a_1,b_1)=(a_2,b_2)$), we have $$0<a^2+b^2<2p\,.$$ As $a^2+b^2$ is divisible by $p$, $a^2+b^2=p$ must hold.