# Method to solve quadratic congruence

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

• 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. – Peter Nov 9 '14 at 12:11
• I do not know, if there is an efficient method to solve the equation $x^2\equiv a\ mod\ (\ p\ )$ in general. – Peter Nov 9 '14 at 12:13

## 1 Answer

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