Existence of Solutions of Quadratic Congruence Using the Law of Quadratic Reciprocity
Example: Does the congruence
\[3x^2-8x-5 \equiv 0 \; (mod \; 139)\]
have solutions? The Discriminant is \[ (-8)^2-4 \times 3 \times 5=124.\]
. Using The Legendre Symbol,\[\begin{equation} \begin{aligned} (124/139) &= (4/139)(31/139) \; (4 \times 31 =124) \\ &=1 \times (31/139) (since \; 4=2^2) \\ &=(-1)(139/31) (by \; the \; law \; of \; quadratic \; reciprocity, \; since \; 31 \equiv 139 \equiv 3 \; (mod \; 4)) \equiv (-1)(15/31) \; (since 139 \equiv 15 \; mod \; 31) \\ &= (-1)(3/31)(5/31) \; (since \; 15 =3 \times 5) \\&= (-1)(-1)(31/3)(5/31) \; (by \; the \; law \; of \; quadratic \; reciprocity, \; since \; 31 \equiv 3 \; (mod \; 4)) \\ & \equiv (31/3)(31/5) \; (by \; the \; law \; of \; quadratic \; reciprocity, \; since \; 5 \equiv 1 \; (mod \; 4)) \\ & \equiv (1/3)(31/5) \; (since \; 31 \equiv 1 \; (mod \; 3)) \\ & \equiv (1/3)(1/5) \; (since \; 31 \equiv 1 \; (mod \; 5) \\ & \equiv 1 \end{aligned} \end{equation}\]
Hence the congruence has solutions.
