What is the general number of solutions of the equation $y^2=x^3-x\pmod{p}$, where $p$ is a prime number and $p>3$?.
Calculations suggest that the number of solutions to this equation is $p$ if $p\equiv 3\pmod{4}$ and the number of solutions is $p-2a$ where $p=a^2+b^2$ and $a\equiv 1\pmod{2}$ if $p\equiv 1\pmod{4}$ .
How do you prove this conjecture?
The question is about determining the number of solutions to $\,y^2=x^3-x\pmod{p}\,$ for a prime $\,p.\,$ This is equivalent to the number of points on the elliptic curve $\,y^2 = x^3 - x\,$ over the finite field with $\,p\,$ elements. This elliptic curve is listed as LMFDB label 32.a3. The number of points are the OEIS sequence A276730 which is for the elliptic curve $\,y^2 = x^3 + 4x\,$ which is listed as LMFDB label 32.a4 but both curves have the same associated modular form listed as LMFDB newform 32.2.a.a whose $q$-expansion is $$ \eta(4z)^2\eta(8z)^2 = q\prod_{n=1}^\infty (1-q^{4n})^2(1-q^{8n})^2 $$ which is listed as OEIS sequence A138515. The criteria is given in OEIS sequence A279392
Your observation
is almost correct except the sign of $\,a\,$ in $\,p=a^2+b^2\,$ depends on if $\,a+b=4k+1\,$ or not (note that the sign of $\,b\,$ does not matter since it is even and $\,b\equiv -b\pmod{4}$). For example, if $\,p=5=1^2+2^2\,$ the number of solutions is $\,7=5+2\cdot 1\,$ since $\,1+2\equiv 3\pmod{4}\,$ while if $\,p=13=3^2+2^2\,$ the number of solutions is also $\,7=13-2\cdot 3\,$ since $\,3+2\equiv 1\pmod{4}.\,$
Your question
is answered by the general theory of elliptic curves. As far as I know there is no easy proof, however in OEIS sequence A095978 is a reference to a theorem in J. H. Silverman, A Friendly Introduction to Number Theory, which you may be able to understand.
The MSE question Number of points on the elliptic curve $y^2 = x^3 - x$ over $\mathbb{F}_q$ has information about possible proofs.