HesapHanem

Quadratic Residue Checker

Enter a value a and a prime modulus p to check quadratic residuosity.

How it is calculated

The tool computes Euler's criterion: r = a(p−1)/2 mod p, using fast modular exponentiation so large values do not overflow. Here a is a non-negative integer and p is the modulus, which must be an odd prime. First a is reduced to a mod p. If that is 0, the symbol is 0 and the verdict reads a ≡ 0. If r = 1, a is a quadratic residue (Legendre symbol +1). Otherwise r = p − 1, a is a non-residue (symbol −1). Values are rounded to whole numbers. The tool gives no result for p = 2, even numbers, composite numbers (checked by trial division) or negative a.

Worked example

Take a = 10 and p = 13. Step 1: (13 − 1) ÷ 2 = 6, so compute 106 mod 13. Step 2: 10² = 100 ≡ 9, 10³ ≡ 9 × 10 = 90 ≡ 12, and 10⁶ ≡ 12² = 144 ≡ 1 (mod 13). Step 3: the Euler value is 1, so the verdict is Quadratic residue and the Legendre symbol is 1. You can confirm it directly: 6² = 36 = 2 × 13 + 10, so x = 6 solves x² ≡ 10 (mod 13).

Try this example →

Common mistakes

  • Entering a composite modulus such as 15. Euler's criterion and the Legendre symbol only apply to primes, and the tool returns no result for them.
  • Expecting −1 in the Euler value. For a non-residue the modular result is shown as p − 1 (12 for p = 13), while the Legendre symbol line shows −1.
  • Confusing a residue with a perfect square. 10 is not a square among ordinary integers but is a residue mod 13, and 4 is a residue modulo every odd prime it is not divisible by.
  • Treating a result of 0 as non-residue. When a is a multiple of p, the symbol is 0 and the verdict is a ≡ 0, a separate case.
  • Assuming that being a residue modulo one prime carries over to another prime. The answer changes with every p.

About this calculator

An integer a is a quadratic residue modulo a prime p if there exists some x such that x² ≡ a (mod p) — in other words, a is a perfect square in modular arithmetic even if it isn't one in ordinary integers. Euler's criterion gives a fast way to test this without searching for x directly: a is a QR mod p if and only if a^((p−1)/2) ≡ 1 (mod p), and a non-residue if it's ≡ −1.

The result is usually expressed as the Legendre symbol (a/p), which is +1, −1, or 0. This calculator computes it, a routine step in number theory coursework and cryptographic algorithms — quadratic residues show up directly in primality tests, in the Tonelli-Shanks algorithm for computing modular square roots, and in some digital signature and zero-knowledge proof constructions.

Was this helpful?

You can pick up to 3 reactions.

Comments (1)

  • Editorial team

    A residue tells you a square root exists, not what it is. When p leaves remainder 3 on division by 4, a root is a raised to (p + 1) ÷ 4, mod p. Try the default a = 5, p = 11: 5³ = 125 leaves 4 modulo 11, and 4² = 16 leaves 5. Are you checking small teaching examples or large primes? Tell us the sizes you need.

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