3

I want to compute a solution of the congruence $$ a^2+b^2\equiv -1\pmod{p}. $$ I know that a solution always exists (this is a simple argument using the pidgeonhole principle). I also know that if $p\equiv 1\pmod{4}$, $-1$ is a quadratic residue mod $p$ and the problem can be solved by calculating a square root $a$ of $-1$ and letting $b=0$.

However, for general $p$, I know of no better method than simply trial and error (which is actually not so bad either since of course the chance to "stumble upon" quadratic residues is about a half). Does anyone know or can anyone think of a more efficient method?

mxian
  • 2,019
  • You are referring to the answer in this post for solvability, right? In Ireland-Rosen's book on number theory they solve it using Jacobi sums for the finite field $\Bbb F_p$. On the other hand, Jyrki's answer is also great, see the duplicate. – Dietrich Burde Sep 03 '21 at 15:13
  • More generally, this post explains how to find all solutions to $ax^2+by^2\equiv -1\bmod p$ in a finite field (replacing $a,b$ by $-a,-b$). – Dietrich Burde Sep 03 '21 at 15:19

0 Answers0