[Math] Sum of nonzero squares modulo p

elementary-number-theorymodular arithmeticnumber theory

It is easy to prove that for prime $p$ every element of $\mathbb{Z} / p \mathbb{Z}$ can be written as the sum of two squares. An elementary proof is given here: Sum of two squares modulo p

How can we show that, provided further $p \geq 7$, any nonzero element of $\mathbb{Z}/ p \mathbb{Z}$ is the sum of two nonzero squares? I don't see how we could extend the counting argument used in the linked post to this case. Thanks

Best Answer

Adapting Mikhail Ivanov's argument to a slightly different but AFAICT equivalent question to fit here. Some of the elements appeared also in my answer to that question.


Every non-zero element of $\Bbb{Z}/p\Bbb{Z}$ is either a square or a non-square If $a=b^2$ is a non-zero square, then, as $p>5$ we have $$ a=b^2=(3b/5)^2+(4b/5)^2 $$ as a sum of two non-zero squares.

On the other hand, if $a$ is a non-zero non-square then $ab^2$ is a non-zero non-square for any $b\neq0$. Furthermore, we get all the non-squares in this way. If $a=x^2+y^2$ with $xy\neq0$, then $ab^2=(bx)^2+(by)^2$, so it suffices to show that we can write at least one of the non-squares as a sum of two non-zero squares. Let's pretend for one time's sake that $\Bbb{Z}/p\Bbb{Z}$ has an "order", so $0<1<2<\ldots<p-1$. Let $a$ be the smallest non-square in this order. Clearly $a>1$. It follows that $a-1=b^2$ is a square, where $b\neq0$. This implies that $a=1+b^2$ is a sum of two non-zero squares. Therefore so are all the other non-squares.