No. Take , . The Jacobi symbol isbut the squares modulo are . A square root of modulo would reduce to one modulo , which is impossible. A Jacobi symbol of records a product of local signs; it does not assert that every local sign is positive, or that a quadratic congruence is soluble.
Complete the square to obtain the equivalent quadratic congruenceHere : the Euclidean algorithm has successive nonzero remainders . If this modular congruence had a solution, the Jacobi symbol would be , since a square coprime to an odd modulus has Legendre symbol at every prime factor. Calculate instead, using Jacobi reciprocity and reduction of numerators,Therefore there is no solution. This obstruction does not require a separate primality test for ; the Jacobi symbol suffices.