# Quadratic residue

A **quadratic residue** modulo a positive integer m is an integer a for which the congruence \( x^2 \equiv a \pmod{m} \) has a solution; when no solution exists, a is a quadratic non-residue of m.<sup>[1](https://math.oxford.emory.edu/site/math125/legendresSymbol/)</sup> The concept, developed for prime moduli by Euler, Legendre, and Gauss, organizes the multiplicative structure of the integers modulo a prime and underlies the law of quadratic reciprocity, primality testing, and several public-key cryptosystems.

| Key fact | Detail |
|---|---|
| Definition | a is a quadratic residue of m when \( x^2 \equiv a \pmod{m} \) is solvable, and a quadratic non-residue otherwise<sup>[1](https://math.oxford.emory.edu/site/math125/legendresSymbol/)</sup> |
| Count modulo a prime | For an odd prime p, exactly half of the \( p-1 \) nonzero residue classes are quadratic residues, namely the even powers of a primitive root g<sup>[2](https://crypto.stanford.edu/pbc/notes/numbertheory/qr.html)</sup> |
| Euler's criterion | For p an odd prime with \( p \nmid a \), a is a residue if and only if \( a^{(p-1)/2} \equiv 1 \pmod{p} \), and a non-residue if and only if \( a^{(p-1)/2} \equiv -1 \pmod{p} \)<sup>[2](https://crypto.stanford.edu/pbc/notes/numbertheory/qr.html)</sup> |
| Legendre symbol | \( \left(\frac{a}{p}\right) \) equals 1 for a nonzero residue, −1 for a non-residue, and 0 when p divides a; it is multiplicative in a<sup>[2](https://crypto.stanford.edu/pbc/notes/numbertheory/qr.html)</sup> |
| Quadratic reciprocity | For distinct odd primes p and q, \( \left(\frac{p}{q}\right)\left(\frac{q}{p}\right) = (-1)^{\frac{p-1}{2}\frac{q-1}{2}} \)<sup>[3](https://dlmf.nist.gov/27.9)</sup> |
| First proof | Gauss proved the reciprocity law in the Disquisitiones arithmeticae (1801), having formulated it independently in March 1795; Euler and Legendre had stated it earlier<sup>[4](https://www.sciencedirect.com/science/chapter/edited-volume/abs/pii/B9780444508713501030)</sup> |
| Cryptographic use | The Goldwasser–Micali probabilistic cryptosystem is secure under the assumption that deciding quadratic residuosity modulo composites of unknown factorization is intractable<sup>[5](https://www.sciencedirect.com/science/article/pii/0022000084900709)</sup> |

## Definition and basic structure

The definition applies to any modulus: if the congruence \( x^2 \equiv a \pmod{m} \) has a solution, a is a quadratic residue of m, and otherwise a quadratic non-residue.<sup>[1](https://math.oxford.emory.edu/site/math125/legendresSymbol/)</sup> Trivially, 1 is a quadratic residue of any modulus, and 0 satisfies \( 0^2 \equiv 0 \) although it is usually excluded from the classification.<sup>[6](https://www.youtube.com/watch?v=WId4kTRet4I)</sup>

For an odd prime p the nonzero classes form a cyclic group. If g is a generator, every nonzero class is \( g^k \) for some k, and \( g^k \) is a square exactly when k is even, since \( x = g^{k/2} \) then solves \( x^2 = g^k \). Exactly half of the nonzero classes are therefore quadratic residues, the even powers of g, and each residue has exactly two square roots, b and −b, because \( b \neq -b \) when \( p > 2 \).<sup>[2](https://crypto.stanford.edu/pbc/notes/numbertheory/qr.html)</sup> For example, 2 is a quadratic residue of 7 since \( 3^2 \equiv 2 \pmod{7} \), but a non-residue of 3.<sup>[6](https://www.youtube.com/watch?v=WId4kTRet4I)</sup>

Residuosity respects factorization. An integer is a quadratic residue modulo a product of distinct odd primes if and only if it is a residue modulo each prime factor, a consequence of the Chinese Remainder Theorem.<sup>[7](https://web.williams.edu/Mathematics/sjmiller/public_html/tas2012CrytpoBenford/unithandouts/unit3alternate_MillerTaklooBighash_Chap1.pdf)</sup>

## Euler's criterion and the Legendre symbol

Euler's criterion gives a direct test. For p an odd prime and \( p \nmid a \),

\[ a^{(p-1)/2} \equiv \left(\frac{a}{p}\right) \pmod{p}, \]

so a is a residue precisely when \( a^{(p-1)/2} \equiv 1 \pmod{p} \) and a non-residue precisely when \( a^{(p-1)/2} \equiv -1 \pmod{p} \).<sup>[2](https://crypto.stanford.edu/pbc/notes/numbertheory/qr.html)</sup><sup> • </sup><sup>[8](https://encyclopediaofmath.org/wiki/Euler_criterion)</sup> The proof exploits that \( a^{(p-1)/2} \) is its own inverse modulo p, and the only classes that are their own inverses modulo a prime are 1 and −1.<sup>[1](https://math.oxford.emory.edu/site/math125/legendresSymbol/)</sup> The criterion is effective in practice: computing \( 773^{686} \bmod 1373 \) by repeated squaring confirms that 773 is a quadratic residue modulo 1373.<sup>[9](https://www.cis.upenn.edu/~jean/RSA-primality-testing.pdf)</sup>

The **Legendre symbol** \( \left(\frac{a}{p}\right) \), also written \( (a|p) \), packages the criterion into a function: it takes the value 1 when a is a nonzero quadratic residue of p, −1 when a is a non-residue, and 0 when p divides a.<sup>[2](https://crypto.stanford.edu/pbc/notes/numbertheory/qr.html)</sup><sup> • </sup><sup>[3](https://dlmf.nist.gov/27.9)</sup> It is multiplicative, \( \left(\frac{a}{p}\right)\left(\frac{b}{p}\right) = \left(\frac{ab}{p}\right) \), and unchanged when a is multiplied by a square coprime to p.<sup>[2](https://crypto.stanford.edu/pbc/notes/numbertheory/qr.html)</sup> As a function of n, the [Legendre symbol](https://www.edgepedia.org/legendre-symbol) is a [Dirichlet character](https://www.edgepedia.org/dirichlet-character) modulo p, the prototype of that class of number-theoretic functions.<sup>[3](https://dlmf.nist.gov/27.9)</sup><sup> • </sup><sup>[10](https://personal.science.psu.edu/rcv4/CENT.pdf)</sup> Two special values follow from the criterion: \( (-1|p) = (-1)^{(p-1)/2} \), so −1 is a residue exactly for primes \( p \equiv 1 \pmod{4} \), and \( (2|p) = (-1)^{(p^2-1)/8} \).<sup>[2](https://crypto.stanford.edu/pbc/notes/numbertheory/qr.html)</sup><sup> • </sup><sup>[3](https://dlmf.nist.gov/27.9)</sup>

## The law of quadratic reciprocity

The **law of quadratic reciprocity** relates residuosity of p modulo q to residuosity of q modulo p. For distinct odd primes p and q,

\[ \left(\frac{p}{q}\right)\left(\frac{q}{p}\right) = (-1)^{\frac{p-1}{2}\frac{q-1}{2}}, \]

so p and q are residues of each other, or non-residues of each other, unless both are congruent to 3 modulo 4, in which case the two symbols disagree.<sup>[3](https://dlmf.nist.gov/27.9)</sup><sup> • </sup><sup>[11](https://crypto.stanford.edu/pbc/notes/numbertheory/quadrecip.html)</sup> The law helps greatly in computing Legendre symbols, since it replaces a large prime denominator with a smaller one.<sup>[11](https://crypto.stanford.edu/pbc/notes/numbertheory/quadrecip.html)</sup> A worked example decides \( \left(\frac{31}{103}\right) \) by repeated application of reciprocity and the special values, concluding that 31 is a quadratic non-residue modulo 103.<sup>[11](https://crypto.stanford.edu/pbc/notes/numbertheory/quadrecip.html)</sup>

**History.** Euler and Legendre noticed the law but obtained only incomplete proofs; Gauss formulated it independently in March 1795 and gave the first complete proof in the Disquisitiones arithmeticae of 1801, where he called it the Theorema Fundamentale.<sup>[4](https://www.sciencedirect.com/science/chapter/edited-volume/abs/pii/B9780444508713501030)</sup><sup> • </sup><sup>[12](https://arxiv.org/abs/math/0504335)</sup> Gauss's own account of his entry into the subject dates his first encounter with such questions to 1795, when he chanced on the theorem of article 108, that −1 is a quadratic residue of all numbers of the form \( 4n+1 \) and a non-residue of all numbers of the form \( 4n+3 \).<sup>[13](https://mathshistory.st-andrews.ac.uk/Extras/Gauss_Disquisitiones/)</sup> The Disquisitiones went on to define the substance and methods of number theory for the following five or six decades and introduced a new approach to binary quadratic forms.<sup>[4](https://www.sciencedirect.com/science/chapter/edited-volume/abs/pii/B9780444508713501030)</sup>

## The Jacobi symbol

The **Jacobi symbol** \( \left(\frac{a}{b}\right) \) extends the Legendre symbol to every odd positive denominator b. If \( b = p_1^{k_1} \cdots p_n^{k_n} \), then \( \left(\frac{a}{b}\right) = \left(\frac{a}{p_1}\right)^{k_1} \cdots \left(\frac{a}{p_n}\right)^{k_n} \), with \( \left(\frac{a}{1}\right) = 1 \).<sup>[11](https://crypto.stanford.edu/pbc/notes/numbertheory/quadrecip.html)</sup> When b is prime it coincides with the Legendre symbol, and the reciprocity law carries over to any two relatively prime odd integers.<sup>[3](https://dlmf.nist.gov/27.9)</sup><sup> • </sup><sup>[11](https://crypto.stanford.edu/pbc/notes/numbertheory/quadrecip.html)</sup>

The extension costs some meaning. For composite b, a Jacobi symbol of +1 does not guarantee that a is a quadratic residue: with \( n = pq \), the value \( \left(\frac{a}{n}\right) = \left(\frac{a}{p}\right)\left(\frac{a}{q}\right) \) equals 1 both when a is a residue of both primes and when it is a non-residue of both, and the latter classes are sometimes called pseudo-squares.<sup>[14](https://algorithms.alexli.ca/jacobi-symbol/)</sup><sup> • </sup><sup>[15](https://zoo.cs.yale.edu/classes/cs467/2012s/lectures/ln14.pdf)</sup> A Jacobi symbol of −1 does prove that a is a non-residue.<sup>[15](https://zoo.cs.yale.edu/classes/cs467/2012s/lectures/ln14.pdf)</sup> The practical advantage is speed: the Jacobi symbol can be computed without factoring, using reciprocity together with the rules for −1 and 2 in the style of the binary GCD, which matters because factoring is generally considered hard.<sup>[14](https://algorithms.alexli.ca/jacobi-symbol/)</sup><sup> • </sup><sup>[9](https://www.cis.upenn.edu/~jean/RSA-primality-testing.pdf)</sup>

## Computation and applications

**Primality testing.** The Solovay–Strassen test, developed in 1978, compares the Jacobi symbol \( \left(\frac{a}{n}\right) \), computed by reciprocity, with \( a^{(n-1)/2} \bmod n \), computed by exponentiation. For a prime the two always agree by Euler's criterion; for a composite, any given residue has at least a 1/2 probability of exposing the compositeness, so a composite passing k trials with random a has probability at most \( 1/2^k \).<sup>[16](https://dummit.cos.northeastern.edu/teaching_sp22_3527/numthy_5_squares_and_quadratic_reciprocity_v3.00.pdf)</sup><sup> • </sup><sup>[15](https://zoo.cs.yale.edu/classes/cs467/2012s/lectures/ln14.pdf)</sup> The Miller–Rabin test, which requires no Jacobi computations, later surpassed it, with a composite passing with probability only 1/4 per trial.<sup>[17](https://crypto.stanford.edu/pbc/notes/numbertheory/carmichael.html)</sup>

**Square roots.** Finding a square root of a residue modulo a prime is done by the Tonelli–Shanks algorithm; Shanks's version needs \( O(\log q + n^2) \) modular multiplications, where \( p - 1 = 2^s t \) with t odd.<sup>[18](https://arxiv.org/abs/1105.1456)</sup> When \( p \equiv 3 \pmod{4} \) the special case \( s = 1 \) is handled directly.<sup>[15](https://zoo.cs.yale.edu/classes/cs467/2012s/lectures/ln14.pdf)</sup> Modulo a composite \( N = pq \) with p and q known, the four square roots of a residue can be found in probabilistic polynomial time; a residue z has exactly four roots of the form \( \{x, N-x, y, N-y\} \) in \( \mathbb{Z}_N^* \).<sup>[19](https://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-2.pdf)</sup>

**Cryptography.** The gap between the Jacobi symbol and true residuosity is the foundation of the quadratic residuosity problem: deciding whether an element with Jacobi symbol 1 modulo a composite of unknown factorization is a square. The Goldwasser–Micali cryptosystem, the first probabilistic public-key scheme, encrypts one-bit messages by multiplying random quadratic residues by a public quadratic non-residue with Jacobi symbol 1, and its security is proved under the intractability of deciding quadratic residuosity modulo composites whose factorization is unknown.<sup>[5](https://www.sciencedirect.com/science/article/pii/0022000084900709)</sup><sup> • </sup><sup>[20](https://www.sciencedirect.com/science/article/pii/S0096300319309853)</sup> The Rabin cryptosystem likewise encrypts messages by quadratic residues.<sup>[20](https://www.sciencedirect.com/science/article/pii/S0096300319309853)</sup>

**Distribution.** How residues and non-residues are distributed among small values is a classical research problem. The least quadratic non-residue \( n_p \) modulo a prime p must be prime; Burgess showed \( n_p = O_{\varepsilon}\big(p^{\frac{1}{4\sqrt{e}}+\varepsilon}\big) \) unconditionally, and under the Generalized Riemann Hypothesis \( n_p < \frac{61}{80}\log^2 p \) for sufficiently large p, a bound whose constant cannot be improved past 0.7596 by the Fourier optimization method used to prove it.<sup>[21](https://arxiv.org/abs/2404.08380)</sup>

## References

1. [Power Residues and Legendre's Symbol, Emory University Math 125](https://math.oxford.emory.edu/site/math125/legendresSymbol/)
2. [Number Theory: Quadratic Residues, Stanford crypto notes](https://crypto.stanford.edu/pbc/notes/numbertheory/qr.html)
3. [DLMF §27.9 Quadratic Characters, NIST](https://dlmf.nist.gov/27.9)
4. [Chapter 22: Carl Friedrich Gauss, Disquisitiones arithmeticae (1801), Landmark Writings in Western Mathematics 1640–1940, ScienceDirect](https://www.sciencedirect.com/science/chapter/edited-volume/abs/pii/B9780444508713501030)
5. [Goldwasser, Shafi, and Micali, Silvio (1984). Probabilistic encryption. Journal of Computer and System Sciences 28(2), 270–299](https://www.sciencedirect.com/science/article/pii/0022000084900709)
6. [Number Theory Lecture 20: Quadratic residue, Euler's Criterion, Legendre Symbol, YouTube](https://www.youtube.com/watch?v=WId4kTRet4I)
7. [Miller, Steven J., and Takloo-Bighash, Ramin, Chapter 1 handout, Williams College](https://web.williams.edu/Mathematics/sjmiller/public_html/tas2012CrytpoBenford/unithandouts/unit3alternate_MillerTaklooBighash_Chap1.pdf)
8. [Euler criterion, Encyclopedia of Mathematics](https://encyclopediaofmath.org/wiki/Euler_criterion)
9. [Notes on Primality Testing, University of Pennsylvania](https://www.cis.upenn.edu/~jean/RSA-primality-testing.pdf)
10. [Chapter 5: Quadratic Residues, Penn State course notes](https://personal.science.psu.edu/rcv4/CENT.pdf)
11. [Number Theory: Quadratic Reciprocity, Stanford crypto notes](https://crypto.stanford.edu/pbc/notes/numbertheory/quadrecip.html)
12. [Notes on Theory of Quadratic Residues, arXiv:math/0504335](https://arxiv.org/abs/math/0504335)
13. [Gauss: Disquisitiones Arithmeticae, MacTutor History of Mathematics](https://mathshistory.st-andrews.ac.uk/Extras/Gauss_Disquisitiones/)
14. [6.3.7 Jacobi Symbol, algorithms.alexli.ca](https://algorithms.alexli.ca/jacobi-symbol/)
15. [CPSC 467b Lecture 14: Quadratic Residues, Yale University](https://zoo.cs.yale.edu/classes/cs467/2012s/lectures/ln14.pdf)
16. [Squares and Quadratic Reciprocity, Northeastern University course notes](https://dummit.cos.northeastern.edu/teaching_sp22_3527/numthy_5_squares_and_quadratic_reciprocity_v3.00.pdf)
17. [Number Theory: Carmichael Numbers, Stanford crypto notes](https://crypto.stanford.edu/pbc/notes/numbertheory/carmichael.html)
18. [On Shanks' Algorithm for Modular Square Roots, arXiv:1105.1456](https://arxiv.org/abs/1105.1456)
19. [NIST Special Publication 800-2, Appendix N: Quadratic residuosity modulo a composite](https://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-2.pdf)
20. [On the distribution of quadratic residues and non-residues modulo composite integers and applications to cryptography, ScienceDirect](https://www.sciencedirect.com/science/article/pii/S0096300319309853)
21. [Fourier optimization, the least quadratic non-residue, and the least prime in an arithmetic progression, arXiv:2404.08380](https://arxiv.org/abs/2404.08380)

---
*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Numbers and algebra › Number theory › Elementary number theory › Quadratic residues and reciprocity*

*Initially written Sep 17, 2026 · Reviewed: Sep 17, 2026; Sep 30, 2026; Oct 15, 2026 · Edited: Sep 30, 2026; Oct 15, 2026 · Last review: Oct 15, 2026*

*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*

License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license