Quadratic Residue Calculator
Determine whether an integer a is a quadratic residue modulo a prime p, and compute the Legendre symbol (a/p). Used in number theory, primality testing, and cryptographic algorithm design.
About this calculator
An integer a is a quadratic residue modulo prime p if there exists an integer x such that x² ≡ a (mod p). The Legendre symbol (a/p) encodes this: it equals 1 if a is a non-zero quadratic residue mod p, −1 if a is a non-residue, and 0 if p divides a. Euler's criterion provides the computational formula: (a/p) = a^((p−1)/2) mod p. If the result is 1, a is a quadratic residue; if the result is p−1 (i.e., −1 mod p), it is a non-residue. This works because the multiplicative group mod p is cyclic of order p−1, and squaring maps exactly half of the non-zero elements to quadratic residues. The calculator evaluates a^((p−1)/2) mod p using fast modular exponentiation.
How to use
Check whether a = 5 is a quadratic residue modulo p = 11. Enter a_value = 5, prime_p = 11, and select 'legendre' as the calculation type. Compute: (p−1)/2 = 5. Calculate 5^5 mod 11 = 3125 mod 11. 3125 ÷ 11 = 284 remainder 1, so 5^5 mod 11 = 1. The Legendre symbol (5/11) = 1, meaning 5 is a quadratic residue mod 11. Indeed, 4² = 16 ≡ 5 (mod 11) confirms this.
Frequently asked questions
What is the difference between a quadratic residue and a quadratic non-residue modulo a prime?
For an odd prime p, the non-zero integers mod p split equally into (p−1)/2 quadratic residues and (p−1)/2 quadratic non-residues. A quadratic residue is any value that appears as x² mod p for some integer x; a non-residue never appears as such a square. For example, mod 7, the squares are 1²=1, 2²=4, 3²=2, giving residues {1, 2, 4} and non-residues {3, 5, 6}. The Legendre symbol (a/p) compactly distinguishes these two classes and 0 when p | a.
How does the Legendre symbol relate to quadratic reciprocity in number theory?
Quadratic reciprocity, proved by Gauss, links the Legendre symbols of two distinct odd primes p and q: (p/q)(q/p) = (−1)^((p−1)/2 × (q−1)/2). This means knowing whether p is a square mod q tells you whether q is a square mod p, up to a sign determined by their residues mod 4. This elegant symmetry is one of the most celebrated theorems in number theory and is used to evaluate Legendre symbols for large primes without direct computation. Generalisations include the Jacobi and Kronecker symbols.
Why is Euler's criterion a^((p−1)/2) mod p used to compute the Legendre symbol?
Fermat's Little Theorem guarantees a^(p−1) ≡ 1 (mod p) for a not divisible by p, so a^((p−1)/2) is a square root of 1 mod p. The only square roots of 1 modulo an odd prime are ±1, i.e., 1 and p−1. If a = x² is a quadratic residue, then a^((p−1)/2) = x^(p−1) ≡ 1 (mod p). If a is a non-residue, the result must be −1 ≡ p−1. This criterion converts a residuosity question into a single modular exponentiation, making it efficient and practical for cryptographic use.