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

Solution 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$.

Solution 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).