Legendre Symbol

Return the Legendre symbol (a/p) for a signed decimal integer and an odd prime p, using Euler’s criterion and trial primality testing limited to p≤10¹².

Description

The Legendre symbol records whether an integer is a quadratic residue modulo an odd prime.

The Legendre symbol records whether an integer is a quadratic residue modulo an odd prime. Its values are zero for divisibility, one for a nonzero square residue and minus one otherwise.^[1]

The tool returns symbol. The indexing and output conventions below determine how to read these values.

When to use Legendre Symbol

Use this for the following task: Return the Legendre symbol (a/p) for a signed decimal integer and an odd prime p, using Euler’s criterion and trial primality testing limited to p≤10¹². Use the input and output conventions below to reproduce the intended mathematical quantity.

How to use Legendre Symbol and understand its results

Choose the required indexes, integers or sequence entries. Preserve decimal-string encodings where the field table specifies strings.
Enter numerator, prime according to the field table, then run the tool.
Read symbol. Use the stated units, indexing and interpretation of the numerical result.
Keep exact decimal strings for subsequent integer arithmetic; distinguish them from any explicitly approximate numeric result.

Input field	Meaning	Value type and bounds	Requirement
numerator	Signed integer a	string (integer/arbitrary); maximum text length 200; pattern ^-?(0\|[1-9][0-9]*)$	Required
prime	Odd prime modulus (resource limit 10^12)	integer; minimum 3; maximum 1000000000000	Required

Require an odd prime modulus, parse the signed numerator as BigInt and normalize its residue into [0,p). Apply Euler’s criterion by exact modular exponentiation.

(a/p) is determined by a^((p−1)/2) mod p

The symbols and boundary conditions refer to the supplied fields and the implementation described above.

Output field	Meaning	Value type
symbol	Legendre symbol	integer

json

{
  "input": {
    "numerator": "5",
    "prime": 11
  },
  "output": {
    "symbol": 1
  }
}

Limitations and assumptions

A composite or even modulus gives an input error. The modulus is at most 10¹²; use the Jacobi or Kronecker tools for their broader domains.

Use the declared integer bounds and string formats. Large exact outputs remain decimal strings; numerical approximations use ordinary floating-point arithmetic. A rejected input is different from a valid zero count or false membership flag.

Alternative or Complementary methods

Choose Jacobi Symbol when you need its operation: Return (a/n) for a signed decimal numerator and positive odd decimal denominator, including (a/1)=1; a value of one does not prove a quadratic residue for composite n. Choose Kronecker Symbol for the complementary operation: Extend the Jacobi symbol to signed decimal denominators, including factors of two, negative denominators, and (a/0)=1 exactly when |a|=1.

Background reference: Arithmetic functions: legendre symbol.

References

Arithmetic functions: legendre symbol — SageMath developers

Similar or alternative tools

Jacobi Symbol
Return (a/n) for a signed decimal numerator and positive odd decimal denominator, including (a/1)=1; a value of one does not prove a quadratic residue for composite n.
Kronecker Symbol
Extend the Jacobi symbol to signed decimal denominators, including factors of two, negative denominators, and (a/0)=1 exactly when |a|=1.