Solve quadratic congruences.

Question

$x^2= -1 (mod 43)$. I want know How to solve this problem and also what will be the general approach for solving any of such quadratic congruences.

Answer 1

It is known the equation $x^2+1\equiv 0\mod p$, $\;p$ an odd prime, has a solution if and only if $p\equiv 1\mod 4$ (quadratic reciprocity, first supplementary law). This supplementary law results from Euler criterion:

If $a$ is a square modulo $p$, $a^{\frac{p-1}2}\equiv 1\mod p$.

If $a$ is not a square modulo $p$, $a^{\frac{p-1}2}\equiv -1\mod p$.