Quadratic Residue and Legendre Symbol Calculator

Calculate (a/p), determine whether a is a square modulo an odd prime p, and find both modular square roots. Inputs stay in your browser.

Enter a and an odd prime p

Commas, spaces, or underscores may group digits in threes. The modulus must be prime; composite and even moduli are rejected.

Result and modular roots

Your result will appear here.

Try a = 10 and p = 13 to see (10/13) = 1 and the roots x ≡ 6 or 7 (mod 13).

Advertisement

What are quadratic residues and the Legendre symbol?

An integer a is a quadratic residue modulo p when some integer x satisfies x2 ≡ a (mod p). Only the remainder of a modulo p matters, so negative and very large values of a can be reduced first.

Legendre symbol: (a/p) = 0 if p | a; 1 if a is a nonzero quadratic residue; −1 if a is a quadratic nonresidue.

Euler’s criterion: a(p−1)/2 ≡ (a/p) (mod p), when p ∤ a.

For a nonzero residue modulo an odd prime, there are exactly two incongruent roots: x and p − x. If p divides a, the symbol is 0 and the only root class is 0.

Worked Legendre symbol examples

Residue: (10/13)

Euler’s criterion gives 106 ≡ 1 (mod 13), so (10/13) = 1. Indeed, 62 ≡ 72 ≡ 10 (mod 13).

Nonresidue: (3/7)

33 ≡ 6 ≡ −1 (mod 7), so (3/7) = −1. The congruence x2 ≡ 3 (mod 7) has no solution.

Divisible case: (14/7)

14 ≡ 0 (mod 7). Therefore (14/7) = 0, and x ≡ 0 (mod 7) is the only root class.

Negative input: (−1/13)

−1 ≡ 12 (mod 13). Since 13 ≡ 1 (mod 4), (−1/13) = 1; the roots are 5 and 8.

Useful Legendre symbol rules

Supplementary laws

(−1/p) = (−1)(p−1)/2

(2/p) = (−1)(p²−1)/8

Thus −1 is a residue exactly when p ≡ 1 (mod 4), and 2 is a residue exactly when p ≡ 1 or 7 (mod 8).

Quadratic reciprocity

(p/q)(q/p) = (−1)(p−1)(q−1)/4

For distinct odd primes p and q, the symbols agree unless both primes are 3 modulo 4, in which case their signs are opposite.

Quadratic residue and Legendre symbol FAQ

What values can a Legendre symbol have?

Only −1, 0, and 1. Zero means the prime p divides a, 1 means a is a nonzero square modulo p, and −1 means it is not a square modulo p.

Why must p be an odd prime?

That is the domain of the Legendre symbol. A related notation, the Jacobi symbol, permits odd composite denominators, but a Jacobi value of 1 does not guarantee that a is a quadratic residue.

How does Euler’s criterion work?

For p ∤ a, exact modular exponentiation evaluates a(p−1)/2 modulo p. The result must be 1 or p − 1. These represent Legendre values 1 and −1 respectively.

Does a residue always have two roots?

A nonzero residue modulo an odd prime has exactly two distinct root classes, x and p − x. The zero residue has only the root class 0.

How are large roots calculated?

The calculator uses Tonelli–Shanks after Euler’s criterion confirms a residue. Modular exponentiation uses browser-native arbitrary-precision integers, so the calculation does not introduce floating-point rounding.

Is this the same as a Jacobi symbol calculator?

No. This tool verifies that p is prime and computes a Legendre symbol. It intentionally rejects composite moduli rather than silently changing the mathematical meaning.

Is my input private?

Yes. Both integers and all intermediate results remain in your browser; the calculator does not upload, save, or add them to the page URL.

Explore more tools