 Computing Legendre symbols by quadratic reciprocity

The practical reward of quadratic reciprocity is a smaller modulus: swap a pair of distinct odd primes, record the required sign, then reduce the numerator by modular arithmetic. Use multiplicativity of the Legendre symbol and the second supplementary law for quadratic reciprocity to handle a factor of two. For example,Here $11,43$ are both $3$ modulo $4$, so the first swap changes sign; $11\equiv 3(\mathrm{mod}8)$ gives $(2/11)=-1$; the swap involving five has no sign change. An independent square check is $21^2=441\equiv 11(\mathrm{mod}43)$. The method determines existence of a square root without itself finding that root.

A composite numerator is allowed in a Legendre symbol; a composite denominator instead calls for a Jacobi symbol. Its Jacobi reciprocity law supports repeated swaps and remainder reductions, in the spirit of the Euclidean algorithm.^[ref]

A final Jacobi symbol of one is not a square-existence certificate for a composite number modulus. For example,yet $x^2\equiv 2(\mathrm{mod}15)$ is impossible: reducing it modulo three would require a square congruent to two, and squares modulo three are only zero or one. The product has hidden two local failures. By contrast, for a prime denominator, a Legendre symbol of one does certify a quadratic residue.