Quadratic Residue Calculator
Determines whether an integer a is a quadratic residue or non-residue modulo a prime p using Euler's criterion. Useful in number theory, cryptography, and primality testing.
About this calculator
An integer a is a quadratic residue modulo a prime p if there exists an integer x such that x² ≡ a (mod p). Euler's criterion provides an efficient test: a is a quadratic residue mod p if and only if a^((p−1)/2) ≡ 1 (mod p). If a^((p−1)/2) ≡ −1 ≡ p−1 (mod p), then a is a quadratic non-residue. If a ≡ 0 (mod p), the result is trivially 0. This criterion follows from Fermat's little theorem, which guarantees a^(p−1) ≡ 1 (mod p), so a^((p−1)/2) is always ±1. Quadratic residues appear in the Legendre symbol, quadratic reciprocity, and algorithms like Tonelli–Shanks for computing modular square roots.
How to use
Determine whether a = 3 is a quadratic residue mod p = 7. Compute the exponent: (7−1)/2 = 3. Calculate 3³ mod 7 = 27 mod 7 = 6. Since 6 = 7−1 = p−1, the result is −1, so 3 is a quadratic non-residue mod 7. Now try a = 2, p = 7: 2³ mod 7 = 8 mod 7 = 1, so 2 is a quadratic residue mod 7. You can verify: 3² = 9 ≡ 2 (mod 7) ✓.
Frequently asked questions
What is the difference between a quadratic residue and a quadratic non-residue?
A quadratic residue modulo p is a number a for which the equation x² ≡ a (mod p) has a solution. A quadratic non-residue has no such solution. For a prime p, exactly (p−1)/2 nonzero residues are quadratic residues and (p−1)/2 are non-residues. For example, mod 7 the quadratic residues are {1, 2, 4} and non-residues are {3, 5, 6}.
How does Euler's criterion relate to the Legendre symbol?
The Legendre symbol (a/p) is a compact notation that equals 1 if a is a quadratic residue mod p, −1 if it is a non-residue, and 0 if p divides a. Euler's criterion shows that (a/p) ≡ a^((p−1)/2) (mod p). This connection makes the Legendre symbol computationally accessible and allows the law of quadratic reciprocity to be stated cleanly in terms of Legendre symbols.
Why are quadratic residues important in cryptography and number theory?
Quadratic residuosity underlies several cryptographic primitives, including the Goldwasser–Micali probabilistic encryption scheme, whose security rests on the hardness of distinguishing quadratic residues from non-residues. In number theory, quadratic residues determine which integers appear as squares in modular arithmetic, driving results like quadratic reciprocity and the structure of finite fields. They also feature in the Tonelli–Shanks and Cipolla algorithms for computing modular square roots.