Quadratic Residue Checker

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.