The computational determination of the Legendre symbol (a|p) for an integer a modulo an odd prime p, producing 1 if a is a quadratic residue mod p (and a ≠ 0 mod p), −1 if a is a nonresidue, and 0 if a ≡ 0 mod p.

Principle

Use multiplicativity and Euler’s criterion: (a|p) ≡ a^{(p−1)/2} (mod p), together with quadratic reciprocity and reduction modulo p to reduce evaluation to smaller residues and known cases.

Demonstration

Example: p = 7, a = 3. Compute 3^{(7−1)/2}=3^3=27≡6≡−1 (mod 7), so (3|7)=−1; hence 3 is a quadratic nonresidue mod 7.

Misapplication

Applying the Legendre symbol formula to composite moduli (treating a Jacobi symbol value as definitive), or assuming (a|p)=1 guarantees a specific square root without checking p or multiplicative inverses.

Consequence

Correct evaluation decides solvability of x^2≡a (mod p), simplifies solving quadratic congruences, and feeds into reciprocity calculations and character sums used across analytic and algebraic number theory.

Reversal

Replacing the Legendre symbol by the Jacobi symbol (mod composite n) inverts decisiveness: a Jacobi value of 1 no longer guarantees quadratic residuosity, demonstrating the contrast between prime and composite modulus indicators.

Boundary

Applies only for integers a and odd prime moduli p (p>2); excludes modulus 2 and composite moduli unless explicitly reinterpreted as the Jacobi symbol; assumes arithmetic in Z/pZ and canonical representatives of classes.

Semantic Tension

Tension exists between the compact algebraic test (Euler’s criterion) and the broader but less decisive Jacobi symbol: one gives exact residuosity for primes, the other is computationally similar but semantically weaker for composites.

Synthesis

Legendre symbol evaluation is an algorithmic and algebraic procedure that, using Euler’s criterion, multiplicativity, and reciprocity, reduces the question of quadratic residuosity modulo an odd prime to finite computations of powers and sign, with clear scope and limits.