Solve $x^2 \equiv -1 \pmod{41} $

Question

Using Legendre's symbol, knowing that $41 \equiv 1 \pmod{4}$ we can solve said equation. Then, I looked at the residue classes and I just counted my way to the solution $x = 9$. Verifying, $9^2 = 81$ and $81 \equiv -1 \pmod{41} $. I was wondering if there was an actual way to solve the equation $$x^2+1 \equiv 0 \pmod{41}$$ using quadratic residue formulas or any other formula for that matter, instead of counting to get the solution.

Answer 1

If $p$ is a prime, and $p\equiv 1\pmod{4}$, then we can express $p$ as the sum of two squares: $p=x^2+y^2$. Then you have $x^2\equiv -y^2\pmod{p}$, and since $\gcd(y,p)=1$, you can find $z$ such that $zy\equiv 1\pmod{p}$. Then $(xz)^2 = x^2z^2 \equiv -y^2z^2 = -1\pmod{p}$.

Here, $41=5^2+4^2$. Now, $4(10)=40\equiv -1\pmod{41}$, so $4(-10)\equiv 1\pmod{41}$. Thus, one solution is $5(-10)= -50\equiv 9\pmod{41}$.

---

Of course, part of this is cheating, since one way to establish that a prime $p$ can be written as a sum of two squares when $p\equiv 1\pmod{4}$ is to rely on the fact that the equation $x^2\equiv -1\pmod{p}$ has a solution.