$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.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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$.
-
$\begingroup$ Can you tell me What do you mean by 'a is square modulo p' $\endgroup$ Commented May 25, 2015 at 9:36
-
1$\begingroup$ There exists $b$ such that $b^2\equiv a \mod p$. $\endgroup$– BernardCommented May 25, 2015 at 9:48