= 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,
$$
\begin{aligned}
\left(\frac{11}{43}\right)
&=-\left(\frac{43}{11}\right)
=-\left(\frac{10}{11}\right)
=-\left(\frac2{11}\right)\left(\frac5{11}\right)\\
&=\left(\frac5{11}\right)
=\left(\frac{11}{5}\right)
=\left(\frac15\right)=1.
\end{aligned}
$$
Here $11,43$ are both $3$ modulo $4$, so the first swap changes sign; $11\equiv3\pmod8$ gives $(2/11)=-1$; the swap involving five has no sign change. An independent square check is $21^2=441\equiv11\pmod{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>.<Quadratic Reciprocity by Ben Lynn>[Ben Lynn, Quadratic Reciprocity, “The Jacobi Symbol”: product definition and reciprocity for computing symbols without factoring]{ref}
A final <Jacobi symbol> of one is not a square-existence certificate for a <composite number> modulus. For example,
$$
\left(\frac2{15}\right)=\left(\frac23\right)\left(\frac25\right)=(-1)(-1)=1,
$$
yet $x^2\equiv2\pmod{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>.
Back to article page
