Given two distinct, odd primes p and q, then p is a quadratic residue modulo q if and only if q is a quadratic residue modulo p, unless p ≡ q ≡ 3 (mod 4), in which case precisely one of p,q is a quadratic residue modulo the other. This was proved by Gauss around 1801 but had been suspected since Euler’s time. As an application, note that it is not immediately obvious whether x² ≡ 31 (mod 257) has a solution, but now note, in terms of the Legendre symbol, that (31|257) = (257|31) = (9|31) = 1 as 9 is clearly a quadratic residue and so 31 is a quadratic residue modulo 257. The theorem does not provide guidance on what the two square roots are—in this case ±51.