The equation $-1 = x^2 + y^2$ in finite fields

Question

In an ordered field we have $x^2 \ge 0$, hence the equation $-1 = x^2 + y^2$ has no solution. But what about finite fields in general? What is the solutions set $$ -1 = x^2 + y^2 $$ of this equation?

Answer 1

Others have explained why there exists at least one solution $P_0=(x_0,y_0)\in \Bbb{F}_q^2$. The standard trick for finding all the solutions goes as follows (see also Lubin's answer).

If $P=(x,y)\in \Bbb{F}_q^2$ is another point on the curve $x^2+y^2+1=0$, then the line $L$ connecting $P_0$ and $P$ is either vertical, when $x=x_0$ and thus $y=\pm y_0$, or it has a slope $t\in\Bbb{F}_q$. In the latter case the equation of the line $L$ is thus $$ y-y_0=t(x-x_0). $$ Plugging the solution $y=t(x-x_0)+y_0$ into the equation $y^2+x^2+1=0$ gives $$ x^2+t^2(x-x_0)^2+2t(x-x_0)y_0+y_0^2+1=0. $$ After expanding and combining equal degree terms we arrive at $$ (t^2+1)x^2+[2ty_0-2t^2x_0]x+[t^2x_0^2-2tx_0y_0+y_0^2+1]=0. $$ Because $P_0$ is on that quadratic curve $x=x_0$ is one solution. From Vieta relations we see that the other solution is thus $$ x=x(t):=-\frac{2ty_0-2t^2x_0}{t^2+1}-x_0. $$ Because the point $P$ was assumed to be on the line $L$, we get $$ y=y(t):=t(x(t)-x_0)+y_0. $$ So we get all the points $P$ of the curve $x^2+y^2=1$ as $P(t)=(x(t),y(t))$ with $t$ ranging over the field $\Bbb{F}_q$, as well as the point $P(\infty)=(x_0,-y_0)$ corresponding to the case of $L$ having an infinite slope. We also observe that if $t^2+1=0$, then the formulas involve division by zero, so we need to throw those values of $t$ away. As a summary:

• If $t^2+1\neq0$ for all $t\in \Bbb{F}_q$ there are exactly $q+1$ solutions $(x,y)\in\Bbb{F}_q^2$.
• If $t^2+1=0$ has two solutions in $\Bbb{F}_q$, then the number of points with coordinates in $\Bbb{F}_q$ on the curve $x^2+y^2+1=0$ is equal to $q-1$.

It is worth remarking that the curve $x^2+y^2+1=0$ has genus zero, so its projective version $X^2+Y^2+Z^2=0$ always has exactly $q+1$ points in $\Bbb{P}^2(\Bbb{F}_q)$. Two of those points will lie on the line at infinity when $-1$ has a square root in $\Bbb{F}_q$.

Answer 2

Let $p$ be an odd prime because the characteristic $2$ case is trivial.

Let $c=-1$ (this value will not matter). As $x$ ranges from $0$ to $p-1$, the polynomial $x^2$ takes $\frac{1}{2}(p+1)$ values (because each value other than $0$ occurs exactly twice, for $x$ and for $-x$). For the same reason, the polynomial $c-y^2$ takes exactly $\frac{1}{2}(p+1)$ values. Since $2 \times \frac{1}{2}(p+1) = p+1 > p$ these two sets of values cannot be disjoint, so there exist $x,y$ such that $x^2 = c - y^2$, i.e. $x^2 + y^2 = c$. So there are always solutions to this equation in $\mathbb{F}_p$. The same reaasoning holds, mutatis mutandis, in $\mathbb{F}_{p^r}$ (of course, for $c=-1$ if $x^2+y^2=-1$ already has a solution in $\mathbb{F}_p$ it certainly has one in $\mathbb{F}_{p^r}$ and we don't need to think further).

Answer 3

Here’s another argument having some ideas similar to those of Gro-Tsen’s.

We may assume that our finite field $k$ is not of characteristic two, say it has $q$ elements, with $q$ a power of an odd prime. If $k$ has a square root of $-1$, we can take the solution $(0,i)$ of our equation, so we can assume there is no $i$ in $k$. It follows that if $z$ is a nonzero square in $k$, then $-z$ is a nonsquare.

Now there are $\frac{q+1}2$ squares, and $\frac{q-1}2$ nonsquares. Thus the squares do not constitute an additive subgroup (because the nontrivial coset would have the same number of elements). Thus there must be a case where the sum of two squares is a nonsquare, in other words, $a^2+b^2=-c^2$. Dividing both sides by $c^2$, we find a solution to the equation.

Answer 4

For a field of order $2^k$, for any $x$ you have $x^2+(x+1)^2=1=-1$.

The multiplicative group of a finite field (of order $p^k$) is cyclic of order $p^k-1$. For $p\neq 2$, this means half of the elements of the multiplicative group are squares and half are not. In general the distribution of these squares over the field may not have a pattern that you can analyze consistently from one prime to the next. But if you think of them as randomly distributed, then for any given $x$, there is a $50\%$ chance that $-1-x^2$ is a square (with two distinct square roots). Thinking this way, you would expect an average of $p^k\cdot\left(2\frac{1}{2}\right)=p^{k}/2$ ordered pairs $(x,y)$ that solve $x^2+y^2=-1$.

Of course this is just speculation, since the distribution of squares is not random in a pure sense.

In any case, how to find solutions? I you are able to calculate square roots in the field, you could just enumerate $x$ through all possible values, and check to find square roots ($y$) of $-1-x^2$.