Explore quadratic residues with an interactive Legendre tool. See validations, reductions, and modular exponentiation details. Download reports, compare examples, and verify prime inputs easily.
For an odd prime p and integer a, the Legendre symbol (a|p) is:
This calculator applies Euler’s criterion: (a|p) ≡ a^((p−1)/2) (mod p). For prime p and gcd(a,p)=1, the result is always 1 or −1.
| a | p | a mod p | (a|p) | Interpretation |
|---|---|---|---|---|
| 5 | 11 | 5 | 1 | Quadratic residue |
| 2 | 7 | 2 | 1 | Quadratic residue |
| 3 | 7 | 3 | -1 | Quadratic non-residue |
| 14 | 7 | 0 | 0 | Divisible by p |
The Legendre symbol (a|p) compresses modular behavior into three outcomes: 0, 1, or −1. For odd prime p, among the p−1 nonzero classes, exactly (p−1)/2 are quadratic residues and (p−1)/2 are non‑residues. If a is chosen uniformly modulo p and not divisible by p, the probability of (a|p)=1 is 50%, which makes the symbol a residue test.
This calculator verifies that p is an odd prime before evaluation. Composite moduli can pass naive checks but break the residue guarantee, because Euler’s criterion is not logically equivalent there. The validator also rejects p=2, where the classical definition is not used in the same way. These safeguards keep every displayed step mathematically consistent.
For gcd(a,p)=1, Euler’s criterion states (a|p) ≡ a^((p−1)/2) (mod p). The implementation reduces a to a mod p, then applies fast modular exponentiation in O(log p) multiplications using square‑and‑multiply. For example, with p=101, the exponent is 50 and the algorithm needs only a small chain of squarings and conditional multiplies, not 50 repeated products.
After computation, the graph shows which classes 0…p−1 are residues. Each residue appears as a marked position, and the tool highlights a mod p so you can see whether it lands inside the residue set. For p up to 2000 the chart renders a full 0/1 residue map; for larger p it switches to a compact scatter of residue locations to keep rendering responsive.
Legendre symbols appear in residue testing, quadratic reciprocity examples, and constructions such as the Blum–Blum–Shub family of ideas. They also arise when deciding whether a square root modulo p exists, a prerequisite for key algorithms that lift solutions from modular equations. In probabilistic settings, the balance between residues and non‑residues is used to model indistinguishability assumptions.
CSV and PDF exports store a, p, a mod p, the symbol, and the classification label. This supports reproducible notebooks, homework verification, and peer review. The exported timestamps provide an audit log, while the on‑screen step list documents reductions and the final congruence a^((p−1)/2) mod p.
Provide any integer a and an odd prime p. The calculator reduces a modulo p, checks primality, then returns 0, 1, or −1 with a residue classification.
Euler’s criterion is guaranteed only for odd primes. With composite moduli the same exponent test can misclassify values, so the calculator rejects non‑prime p to keep results valid.
A result of 0 means p divides a, so a ≡ 0 (mod p). In that case a is neither a nonzero residue nor non‑residue class modulo p.
The tool uses fast modular exponentiation (square‑and‑multiply), which needs about log2(p) squaring steps. This is far faster than multiplying a repeatedly (p−1)/2 times.
It visualizes quadratic residues modulo p. The marked positions are residues, and the highlighted marker indicates a mod p, letting you verify the classification at a glance.
Use exports when you need a record for assignments, reports, or review. CSV is ideal for spreadsheets, while PDF is convenient for sharing a fixed summary with the key values.
Important Note: All the Calculators listed in this site are for educational purpose only and we do not guarentee the accuracy of results. Please do consult with other sources as well.