legendre symbol calculator

What is the Legendre symbol?

The Legendre symbol is a compact way to say whether an integer is a quadratic residue modulo an odd prime. For odd prime p and integer a, the symbol is:

• (a/p) = 0 if p divides a
• (a/p) = 1 if a is a quadratic residue mod p
• (a/p) = -1 if a is a quadratic non-residue mod p

In plain language: if there exists some integer x such that x² ≡ a (mod p), then the value is 1. If no such x exists, it is -1. If a ≡ 0 (mod p), it is 0.

How this calculator works

1) Input validation

The calculator first checks that both inputs are integers, then verifies that p is an odd prime. If p is not prime or is even, the Legendre symbol is not defined and you get an error message.

2) Modular reduction

Since only the residue class of a modulo p matters, the calculator reduces a to a mod p. This also handles negative values cleanly.

3) Euler’s criterion

For odd prime p, Euler’s criterion states: a^(p-1)/2 ≡ (a/p) (mod p). So the calculator computes the modular power using fast exponentiation:

• If result is 1, then (a/p)=1
• If result is p-1, then (a/p)=-1
• If a ≡ 0 (mod p), then (a/p)=0

Worked examples

Example A: (5/11)

Squares mod 11 are: 1, 4, 9, 5, 3. Because 5 appears in that list, 5 is a quadratic residue mod 11, so: (5/11)=1.

Example B: (2/7)

Squares mod 7 are: 1, 2, 4. Since 2 is in the list, (2/7)=1.

Example C: (-3/13)

First reduce: -3 ≡ 10 (mod 13). Then check whether 10 is a square mod 13. It is not, so (-3/13)=-1.

Key properties worth remembering

• Multiplicativity: (ab/p) = (a/p)(b/p)
• Dependence on residue class: if a ≡ b (mod p), then (a/p)=(b/p)
• Special values: formulas exist for (-1/p) and (2/p)
• Quadratic reciprocity: connects (p/q) and (q/p) for odd primes

Why it matters

Legendre symbols show up in number theory, primality testing ideas, finite fields, and cryptography. They are fundamental when studying quadratic congruences and are often the first step toward understanding the Jacobi symbol, quadratic reciprocity, and more advanced algebraic number theory topics.

Common mistakes

• Using a composite modulus (for that, use the Jacobi symbol instead)
• Forgetting that p must be odd and prime
• Not reducing negative a values modulo p first
• Confusing p-1 in modular output with numeric value -1