1
$\begingroup$

I learned quadratic congruence by myself and stuck in these problems:

  1. I know if quadratic congruence $X^2=a(\mod\mbox{ p} )$ with $p$ is an odd prime number and $\gcd(a,p)=1$, then it has no solution or has exactly two solutions. So, what is Theorem/Lemma that guarantee a quadratic congruence has solutions?

  2. For linear congruence, we can use the extended Euclidean algorithm to find solution of linear congruence. So my question, what is method to find solution of quadratic congruence?

I would really appreciate if anyone could help me out here

$\endgroup$
  • $\begingroup$ Look at quadratic residues to find the details how it can be determined when the equation $x^2\equiv a\ mod\ (\ p\ )$ is solveable. Some other keywords : legendre-symbol, kronecker-symbol. $\endgroup$ – Peter Nov 9 '14 at 12:11
  • $\begingroup$ I do not know, if there is an efficient method to solve the equation $x^2\equiv a\ mod\ (\ p\ )$ in general. $\endgroup$ – Peter Nov 9 '14 at 12:13
1
$\begingroup$

The main result about this matter is the Quadratic reciprocity's Law. You should learn also about Jacobi symbol.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.