How to use the legendre and jacobi symbol calculator
- Enter the whole number a. It can be negative or very large, up to 40 digits.
- Enter the odd modulus n, a whole number of 3 or more. When n is prime the answer is the Legendre symbol; otherwise it is the Jacobi symbol.
- Read the symbol: 1, -1 or 0, with a one-line meaning.
- For a prime n, also read Euler's criterion and, when a is a square, its two square roots modulo n.
Formula
Legendre symbol (a / p) = 1 if a is a nonzero square mod p, -1 if it is not, and 0 if p divides a
Euler's criterion: (a / p) = a^((p-1)/2) mod p, read as 1, -1 or 0
Jacobi symbol (a / n) = the product of (a / p) over the prime factors of n, counted with multiplicity
Quadratic reciprocity: (a / n)(n / a) = -1 only when a and n are both 3 mod 4; (2 / n) = -1 when n is 3 or 5 mod 8
The symbol is computed with the reciprocity rules, so n never has to be factored. A Jacobi value of 1 for a composite n does not prove that a is a square.
A residue, a non-residue and a trap
Modulo the prime 11, the number 5 is a square because 4 x 4 = 16 = 5 (mod 11), so (5 / 11) = 1 and the square roots are 4 and 7. Modulo 17, the number 2 is a square because 6 x 6 = 36 = 2 (mod 17), so (2 / 17) = 1 with roots 6 and 11. The number -1 is a square modulo 101, with roots 10 and 91, and (3 / 7) = -1 because 3 is not a square modulo 7. For the prime 9907 the symbol (1001 / 9907) is -1, and Euler's criterion shows 1001^4953 = 9906 = -1 (mod 9907).
The trap is a composite modulus. The Jacobi symbol (2 / 15) equals (2 / 3) times (2 / 5), which is -1 times -1 = 1, yet 2 is not a square modulo 15, because the squares modulo 15 are only 1, 4, 6, 9 and 10. When the symbol is -1 the number is surely not a square, but when it is 1 for a composite n you cannot conclude it is one.
Reading the result
A symbol of 1 for a prime means a is a quadratic residue: some x has x squared equal to a modulo p. A symbol of -1 means no such x exists. A symbol of 0 means a and n share a factor. These facts decide whether equations such as x squared = a (mod p) can be solved, and they are the first step of algorithms for primality testing and for finding square roots.
The page also gives the square roots when n is prime and a is a residue. It uses the Tonelli-Shanks algorithm, which works for every odd prime, including those where p is 1 mod 4 and a simple formula is not available. The two roots always add up to n.
Related ideas
Quadratic residues are connected to primitive roots: a is a residue exactly when its discrete logarithm to a primitive root is even. See the primitive root and discrete logarithm calculator to explore that link. For sums of two squares, which also depend on primes that are 1 mod 4, use the sum of two squares calculator.
For the arithmetic behind the scenes, the modular arithmetic calculator computes powers and inverses, and the prime number calculator factors a number.
Assumptions and limits
- n must be odd and at least 3. The Kronecker extension to even n is not included.
- a and n can have up to 40 digits. Primality of n is tested exactly below 10^24 and not tested above it.
- Square roots are shown only when n is a tested prime and a is a nonzero residue.
- All arithmetic is exact, with no floating point.
Frequently asked questions
What is the Legendre symbol?
It tells whether a number is a square modulo an odd prime p. It is 1 for a nonzero square, -1 for a non-square and 0 when p divides the number.
How is the Jacobi symbol different?
It extends the idea to any odd modulus by multiplying the Legendre symbols of its prime factors. It follows the same reciprocity rules, but a value of 1 no longer guarantees a square.
How are the square roots found?
With the Tonelli-Shanks algorithm for primes. The two roots are x and n - x, and the page lists them in increasing order.
Can I use a negative number?
Yes. It is reduced modulo n first, so -1 modulo 101 is treated as 100.