HesapHanem

Legendre Symbol Calculator

Enter an integer a and an odd prime p to compute the Legendre symbol.

How it is calculated

The Legendre symbol (a/p) tells you whether x² ≡ a (mod p) has a solution for an odd prime p. The tool uses Euler's criterion: it computes a^((p−1)/2) mod p by repeated squaring, which is fast even for large p. The outcome is 1 if the power is 1 (a is a square modulo p), -1 if it is p − 1 (a is not a square) and 0 if p divides a. Negative a is allowed; it is first reduced into the range 0 to p − 1. Both a and p must be whole numbers. The tool checks that p is an odd prime no larger than 1,000,000,000 and returns nothing otherwise, so p = 2, composite numbers and larger primes such as 1,000,000,007 are not accepted.

Worked example

Find (3/7). Here (p − 1) ÷ 2 = 3, so we need 3³ mod 7. 3³ = 27, and 27 − 3 × 7 = 6, which is the same as 7 − 1, i.e. −1 modulo 7. The Legendre symbol is therefore -1. A direct check agrees: the squares modulo 7 are 1² = 1, 2² = 4 and 3² = 9 ≡ 2, so only 1, 2 and 4 are squares and 3 is not. By contrast, (2/7) = 1, because 2 is on that list.

Try this example →

Common mistakes

  • Entering a composite modulus such as 9 or 15: the symbol is defined for a prime p only, and the tool returns no result; the Jacobi symbol, a different function, would be needed.
  • Reading 0 as "no solution": 0 means p divides a, in which case x = 0 is actually the solution of x² ≡ a.
  • Reading -1 as "a is negative" or "x is negative"; it means a is a quadratic non-residue, so no integer x satisfies x² ≡ a (mod p).
  • Using the symbol to count solutions: when it is 1 there are exactly two solutions x and p − x, but the tool does not find them.
  • Entering a decimal or a fraction for a or p, or p = 2: both a and p must be integers and p must be an odd prime.

About this calculator

The Legendre symbol (a/p), defined for an integer a and an odd prime p, is a compact way of answering a fundamental question in number theory: does the congruence x² ≡ a (mod p) have a solution? This calculator evaluates it using Euler's criterion: (a/p) ≡ a^((p-1)/2) (mod p), which equals 1 if a is a quadratic residue mod p, −1 if it is a non-residue, and 0 if p divides a exactly.

The Legendre symbol is a building block of quadratic reciprocity theory and shows up throughout computational number theory and cryptography — including primality tests, algorithms for computing modular square roots, and constructions in elliptic-curve cryptography — wherever it matters whether a number is a perfect square modulo a prime.

Was this helpful?

You can pick up to 3 reactions.

Comments (1)

  • Editorial team

    Two supplementary rules give a quick check on the tool. The symbol (−1/p) is 1 exactly when p leaves remainder 1 on division by 4, and (2/p) is 1 exactly when p leaves remainder 1 or 7 on division by 8. So (−1/13) is 1, (−1/11) is −1, (2/7) is 1 and (2/11) is −1, all of which the tool returns. Are you using it for number theory homework or for something like modular square roots in code?

Popular calculators

Loan Calculator

Monthly payment, total interest and full amortization schedule.

Percentage Calculator

Percent change, percent of, and ratio calculations.

Discount Calculator

Calculate final price, savings, and discount amount.

BMI Calculator

Body mass index from height and weight (metric or imperial).

Age Calculator

Compute your exact age in years, months and days from a birth date.

Compound Interest Calculator

Calculate the final amount and interest earned with compounding.

All Calculators