In mathematics, a number q is called a quadratic residue modulo n if there exists an integer x such that:

$\{q\}\backslash equiv\{x^2\}\backslash mbox\{\; (mod\; \}n\backslash mbox\{)\}.$

Otherwise, q is called a quadratic non-residue. For prime moduli, roughly half of the residue classes are of each type. More precisely, for prime p > 2, there are

(p − 1)/2

of each kind, excluding 0. They occur in a rather random pattern; this has been exploited in applications to acoustics.

In effect, a quadratic residue modulo n is a number that has a square root in modular arithmetic when the modulus is n. This concept plays a large part in classical number theory.

Complexity of Finding Square Roots

---

The problem of finding a square root in modular arithmetic, in other words solving the above for x given q and n, can be a difficult problem. For general composite n, the problem is known to be equivalent to integer factorization of n (an efficient solution to either problem could be used to solve the other efficiently). On the other hand, if we want to know if there is a solution for x less than some given limit c, this problem is NP-complete (Adleman, Manders 1978); however, this is a fixed-parameter tractable problem, where c is the parameter.

See also

---

• congruence of squares
• distribution of quadratic residues
• Gauss's lemma
• law of quadratic reciprocity
• Legendre symbol
• Paley graph
• quadratic residuosity problem
• Zolotarev's lemma

References

---

• A7.1: AN1, pg.249.

External links

---

• MathWorld: Quadratic Residue

Modular arithmetic

Quadratischer Rest | residuo cuadrático | Résidu quadratique | שארית ריבועית | 平方剰余 | Reszta kwadratowa | Neliöjäännös | Kvadratisk rest | 二次剩余