Main Calculator
Enter integers a and n to evaluate whether x² ≡ a (mod n) has a solution.
Enter values and click Calculate to begin.
Instantly check whether a number a is a quadratic residue modulo n, list all modular square roots, and understand the theory with a complete long-form guide designed for students, coders, and number theory enthusiasts.
Enter integers a and n to evaluate whether x² ≡ a (mod n) has a solution.
Generate all distinct values of x² mod n for x = 0 ... n-1. Useful for pattern exploration and exam prep.
A quadratic residue modulo n is an integer that can be written as a square in modular arithmetic. In plain language, a is a quadratic residue mod n if there exists at least one integer x such that:
x² ≡ a (mod n)
If no such integer exists, then a is called a quadratic non-residue modulo n. This concept appears everywhere in number theory, cryptography, coding theory, and competitive mathematics. A quadratic residue calculator helps you test values quickly and verify by listing all roots.
This page gives two practical tools. The first checks whether your chosen value a is a residue mod n. It also normalizes a into the standard interval 0 ≤ a < n, so you can enter negative values or large numbers safely. The calculator then tries to find all roots x with x² ≡ a (mod n).
The second tool generates the full residue set modulo n, which is the set of all distinct outcomes of x² mod n. This is excellent for learning symmetry properties and spotting structure in modular squares.
Quadratic residues are not just textbook definitions. They are practical and foundational in real systems. In cryptography, hardness assumptions often rely on deciding whether a value is a square modulo a composite number. In algorithm design, residue tests can speed up primality and congruence filtering. In mathematical proofs, residues provide elegant pathways to classify solvability of equations.
For students, a calculator makes it much easier to build intuition. You can test dozens of examples rapidly, compare prime vs composite behavior, and see how root counts change with modulus structure.
To solve x² ≡ a (mod n), you need integers where the difference x² - a is divisible by n. If at least one exists, a is a residue.
When p is an odd prime and a is not divisible by p, Euler’s criterion states:
a^((p-1)/2) ≡ 1 (mod p) if a is a residue
a^((p-1)/2) ≡ -1 (mod p) if a is a non-residue
This gives a fast test without checking every possible x.
The Legendre symbol summarizes residue status for odd primes:
(a/p) = 1, 0, or -1
For composite n, behavior is richer. Some numbers may have multiple roots, and criteria are less direct. Brute-force or decomposition methods are typically used. This calculator handles small and medium moduli exactly by root search.
| Equation | Result | Roots | Interpretation |
|---|---|---|---|
| x² ≡ 10 (mod 13) | Residue | x ≡ 6, 7 | Because 6² = 36 ≡ 10 and 7² = 49 ≡ 10. |
| x² ≡ 3 (mod 7) | Non-residue | None | No square mod 7 equals 3. |
| x² ≡ 1 (mod 8) | Residue | 1, 3, 5, 7 | Composite moduli can produce more than two roots. |
Yes. For prime moduli, nonzero residues usually have two roots. For composite moduli, the number of roots can be 0, 2, 4, or more depending on factorization and the target value.
The calculator converts it to the equivalent positive residue class using normalization, so results remain mathematically correct.
Yes. Root search works directly for small and medium composite moduli. For very large composite moduli, complete root enumeration can be computationally expensive.
For large values of n, exhaustive root listing may be intentionally limited for speed. If n is prime, Euler-based classification still provides reliable residue status quickly.
A strong grasp of quadratic residues unlocks a major part of modular arithmetic. Whether your goal is exam performance, algorithm design, or cryptography, this quadratic residue calculator gives both speed and conceptual support. Test values, inspect root structure, and use the theory sections to connect computation with proof-level understanding.