Quadratic residue
In number theory, a quadratic residue modulo an integer n is a nonzero integer a coprime to n for which the congruence x^2 \equiv a \pmod{n} has a solution in integers x.[1] This concept distinguishes elements that are perfect squares in the multiplicative group modulo n from those that are not, playing a foundational role in the study of modular arithmetic and Diophantine equations.[1] The theory of quadratic residues originated in the 17th century with Pierre de Fermat's investigations into sums of squares and conditions under which primes could be expressed in specific quadratic forms, though without formal proofs. In the 18th century, Leonhard Euler advanced the subject by proving several of Fermat's claims and conjecturing the law of quadratic reciprocity, a pivotal result linking the quadratic residuosity of primes modulo each other. Carl Friedrich Gauss provided the first complete proof of quadratic reciprocity in his 1801 Disquisitiones Arithmeticae, unifying scattered results into a coherent framework that revolutionized number theory and earned the law the title of its "most beautiful" theorem.[2] For an odd prime p and a not divisible by p, exactly (p-1)/2 nonzero residues modulo p are quadratic residues, a fact that underscores their balanced distribution in finite fields.[3] Central to the topic is the Legendre symbol \left( \frac{a}{p} \right), defined as 1 if a is a quadratic residue modulo p, -1 if a quadratic nonresidue, and 0 if p divides a; it satisfies multiplicativity and is computable via Euler's criterion, which states \left( \frac{a}{p} \right) \equiv a^{(p-1)/2} \pmod{p}.[3] The law of quadratic reciprocity asserts that for distinct odd primes p and q, \left( \frac{p}{q} \right) \left( \frac{q}{p} \right) = (-1)^{(p-1)/2 \cdot (q-1)/2}, enabling efficient determination of quadratic residuosity without exhaustive search.[3] Special cases include -1 being a quadratic residue modulo p if and only if p \equiv 1 \pmod{4}, and 2 being one if p \equiv 1 or $7 \pmod{8}.[3] Quadratic residues find extensive applications in modern mathematics and computing, particularly in primality testing algorithms like the Solovay-Strassen test, which leverages Euler's criterion to probabilistically verify primality.[3] In cryptography, the quadratic residuosity problem—distinguishing residues from nonresidues modulo a composite n without knowing its factorization—underlies the security of the Goldwasser-Micali cryptosystem, a probabilistic public-key encryption scheme introduced in 1982.[4] These uses highlight the concept's enduring relevance in securing digital communications and advancing computational number theory.Definition and Basic Concepts
Definition
In number theory, an integer a is defined as a quadratic residue modulo n if there exists an integer x such that x^2 \equiv a \pmod{n} and \gcd(a, n) = 1.[5] If no such x exists under the coprimality condition, then a is a quadratic nonresidue modulo n.[5] When \gcd(a, n) > 1, a is neither a residue nor a nonresidue in this context, though the case a \equiv 0 \pmod{n} is sometimes regarded as a trivial quadratic residue since $0^2 \equiv 0 \pmod{n}.[6] This distinction relies on basic modular arithmetic, where congruence relations partition integers into residue classes. For illustration, consider n = 5: the squares modulo 5 are $0^2 \equiv 0, $1^2 \equiv 1, $2^2 \equiv 4, $3^2 \equiv 4, and $4^2 \equiv 1, yielding quadratic residues 0, 1, and 4 (with 0 trivial and 1, 4 coprime to 5).[5] The integers 2 and 3, coprime to 5 but not squares, are quadratic nonresidues.[5] Within the multiplicative group (\mathbb{Z}/n\mathbb{Z})^* of units modulo n, the quadratic residues (excluding 0) form a subgroup when n is prime; specifically, for an odd prime p, this subgroup has index 2, comprising exactly (p-1)/2 elements out of the p-1 units.[7]Notations
The Legendre symbol \left( \frac{a}{p} \right) is a standard notation in number theory for an integer a and an odd prime p, defined to equal 0 if p divides a, 1 if a is a quadratic residue modulo p with \gcd(a, p) = 1, and -1 if a is a quadratic non-residue modulo p.[8] This symbol is completely multiplicative in the upper argument, satisfying \left( \frac{ab}{p} \right) = \left( \frac{a}{p} \right) \left( \frac{b}{p} \right) for any integers a and b.[8] Euler's criterion provides a computational relation: \left( \frac{a}{p} \right) \equiv a^{(p-1)/2} \pmod{p} when p \nmid a.[9] The Jacobi symbol \left( \frac{a}{n} \right) generalizes the Legendre symbol to an odd positive integer n > 1 and integer a, defined via the prime factorization n = p_1^{k_1} \cdots p_r^{k_r} as \left( \frac{a}{n} \right) = \prod_{i=1}^r \left( \frac{a}{p_i} \right)^{k_i}, where each \left( \frac{a}{p_i} \right) is the Legendre symbol; it equals 0 if \gcd(a, n) > 1.[10] When n is prime, the Jacobi symbol coincides with the Legendre symbol, but in general, \left( \frac{a}{n} \right) = 1 does not imply that a is a quadratic residue modulo n.[10] Like the Legendre symbol, the Jacobi symbol is completely multiplicative in both arguments.[10] The Kronecker symbol extends the Jacobi symbol to arbitrary integers n, denoted \left( \frac{a}{n} \right) or \left( \frac{a}{n} \right)_K, and is defined to match the Jacobi symbol when n > 0 is odd, with additional rules for n = -1 and n = 2: \left( \frac{a}{-1} \right) = (-1) if a < 0 and 1 if a \geq 0; \left( \frac{a}{2} \right) = 0 if a is even, 1 if a \equiv \pm 1 \pmod{8}, and -1 if a \equiv \pm 3 \pmod{8}.[11] It preserves multiplicativity and serves as a quadratic character modulo any integer discriminant.[11] Standard conventions for these symbols treat the upper argument a as any integer, often reduced modulo |n| for computation, with negative values handled via multiplicativity: for example, \left( \frac{-a}{p} \right) = \left( \frac{-1}{p} \right) \left( \frac{a}{p} \right) where \left( \frac{-1}{p} \right) = (-1)^{(p-1)/2}.[8] The Legendre and Jacobi symbols are undefined for the even prime 2, but the Kronecker symbol accommodates it directly.[11]Properties and Elementary Facts
Modulo a Prime
When the modulus is a prime p, quadratic residues exhibit particularly simple and well-understood properties due to the structure of the multiplicative group (\mathbb{Z}/p\mathbb{Z})^\times. For an odd prime p, the nonzero quadratic residues modulo p are precisely the squares of the nonzero elements in \mathbb{Z}/p\mathbb{Z}, and there are exactly (p-1)/2 such distinct residues.[12] These form a subgroup of index 2 in (\mathbb{Z}/p\mathbb{Z})^\times, which has order p-1, reflecting the fact that the squaring map is a 2-to-1 homomorphism onto this subgroup.[13] A fundamental characterization is given by Euler's criterion, which states that for an odd prime p and an integer a not divisible by p, a is a quadratic residue modulo p if and only if a^{(p-1)/2} \equiv 1 \pmod{p}. If instead a^{(p-1)/2} \equiv -1 \pmod{p}, then a is a quadratic non-residue modulo p. This criterion follows from properties of the multiplicative group and Fermat's Little Theorem, providing an efficient computational test for residuosity.[14] Gauss's lemma offers another key perspective, relating the Legendre symbol (a/p) to the least absolute residues of multiples of a. Specifically, for an odd prime p and a coprime to p, consider the integers a, 2a, \dots, ((p-1)/2)a reduced modulo p to their least absolute residues (between -p/2 and p/2). Let n be the number of these residues that are negative. Then (a/p) = (-1)^n, so a is a quadratic residue if and only if n is even. This lemma underpins many proofs in the theory and highlights the parity of sign changes in the residues.[15] In terms of structure, every nonzero quadratic residue modulo an odd prime p has exactly two distinct square roots in \mathbb{Z}/p\mathbb{Z}, namely x and -x for any square root x, since the equation y^2 \equiv a \pmod{p} with a \not\equiv 0 \pmod{p} has precisely two solutions by the group properties. This contrasts with the zero residue, which has a unique square root, namely 0. The set of quadratic residues and non-residues each has size (p-1)/2, and multiplication by a fixed quadratic non-residue establishes a bijection between them, as it maps the subgroup of residues to its coset of non-residues.[16] The case modulo 2 is exceptional and simpler: the quadratic residues are 0 and 1, since $0^2 \equiv 0 \pmod{2} and $1^2 \equiv 1 \pmod{2}, with every integer congruent to one of these. For small odd primes, explicit examples illustrate these properties; modulo 5, the nonzero residues are 1 and 4 (from $1^2 \equiv 1, $2^2 \equiv 4, $3^2 \equiv 4, $4^2 \equiv 1); modulo 7, they are 1, 2, and 4 (from squares yielding these values). Such computations confirm the count and subgroup structure for primes like the Fermat prime 5 or 17.[17]Modulo a Prime Power
When considering quadratic residues modulo a prime power p^k where p is an odd prime and a is coprime to p, a is a quadratic residue modulo p^k if and only if it is a quadratic residue modulo p.[18] This equivalence follows from the ability to lift solutions of the congruence x^2 \equiv a \pmod{p} to higher powers using Hensel's lemma.[19] To apply Hensel's lemma, consider the polynomial f(x) = x^2 - a. Suppose x_0 is a solution modulo p, so f(x_0) \equiv 0 \pmod{p}. The derivative is f'(x) = 2x, and since p is odd, $2 \not\equiv 0 \pmod{p}. Moreover, as a \not\equiv 0 \pmod{p}, x_0 \not\equiv 0 \pmod{p}, ensuring f'(x_0) = 2x_0 \not\equiv 0 \pmod{p}. Thus, each of the two distinct solutions modulo p lifts uniquely to a solution modulo p^k, yielding exactly two solutions modulo p^k.[19][18] For example, consider x^2 \equiv 1 \pmod{9} where p=3 and k=2. Modulo 3, the solutions are x \equiv 1 \pmod{3} and x \equiv 2 \pmod{3} (since $2 \equiv -1 \pmod{3}). Applying Hensel's lemma lifts these to x \equiv 1 \pmod{9} and x \equiv 8 \pmod{9} (since $8 \equiv -1 \pmod{9}), confirming two solutions.[18] The case p=2 requires separate treatment due to the even characteristic. Modulo 8 ($2^3), the quadratic residues are 0, 1, and 4.[20] For odd a, only 1 is a quadratic residue modulo 8. Modulo 16 ($2^4), the odd quadratic residues are 1 and 9. In general, for k \geq 3, the odd quadratic residues modulo $2^k are precisely the integers congruent to 1 modulo 8, and there are $2^{k-3} such residues.[20] Each such residue has exactly four solutions modulo $2^k.[20] For instance, x^2 \equiv 2 \pmod{8} has no solutions, as 2 is not among the quadratic residues modulo 8. Solutions can sometimes lift further, but the condition for being a quadratic residue modulo $2^k is stricter than for odd primes and depends on congruence classes modulo 8.[20]Modulo a Composite
When the modulus n is composite, say n = \prod_{i=1}^t p_i^{k_i} where the p_i are distinct primes and k_i \geq 1, an integer a is a quadratic residue modulo n if and only if the congruence x^2 \equiv a \pmod{n} has a solution, which by the Chinese Remainder Theorem is equivalent to the congruence having a solution modulo each prime power factor p_i^{k_i}.[21][18] This decomposition follows from the ring isomorphism \mathbb{Z}/n\mathbb{Z} \cong \prod_{i=1}^t \mathbb{Z}/p_i^{k_i}\mathbb{Z}, which implies that solvability in the product ring holds precisely when it holds componentwise.[18] For the multiplicative group of units, (\mathbb{Z}/n\mathbb{Z})^\times \cong \prod_{i=1}^t (\mathbb{Z}/p_i^{k_i}\mathbb{Z})^\times, so quadratic residuosity for a coprime to n likewise decomposes across the factors.[3] Assuming \gcd(a, n) = 1, the Jacobi symbol (a/n) provides a necessary condition for a to be a quadratic residue modulo n: if a is a quadratic residue modulo n, then (a/n) = 1.[3][21] However, this condition is not sufficient, as (a/n) = 1 does not guarantee the existence of a solution to x^2 \equiv a \pmod{n}.[3] For instance, consider n = 15 = 3 \times 5; here, the quadratic residues modulo 15 among the units are 1 and 4, which are precisely those a coprime to 15 that are quadratic residues modulo both 3 and 5.[21] Yet, a = 2 satisfies (2/15) = (2/3)(2/5) = (-1)(-1) = 1, but 2 is not a quadratic residue modulo 15, since it fails to be one modulo 3 (where the nonzero squares are only 1) and modulo 5 (where they are 1 and 4).[3][21] If a is a quadratic residue modulo each p_i^{k_i}, the total number of solutions to x^2 \equiv a \pmod{n} is the product of the number of solutions modulo each p_i^{k_i}.[21] For example, when n is square-free (i.e., k_i = 1 for all i and all p_i odd), and a is coprime to n, there are exactly $2^t solutions if a is a quadratic residue modulo n, corresponding to choices of square roots in each \mathbb{Z}/p_i\mathbb{Z}.[21] In the case of multiple distinct odd prime factors, the proportion of quadratic residues among units modulo n is \frac{1}{2^t}, reflecting the balanced decomposition across factors.[21]Historical Development
Early Contributions
In the European Renaissance, Pierre de Fermat (1607–1665) initiated systematic study of squares modulo primes through his correspondence and unpublished notes. In a 1640 letter to Marin Mersenne, Fermat stated his little theorem—that if p is prime and a not divisible by p, then a^{p-1} \equiv 1 \pmod{p}—which underpins criteria for quadratic residues, as the exponent (p-1)/2 distinguishes residues from non-residues. He also asserted that an odd prime p is a sum of two squares if and only if p \equiv 1 \pmod{4}, equivalent to -1 being a quadratic residue modulo p, and examined residues modulo small primes like 5 and 13, noting patterns such as the quadratic residues modulo 5 being 0, 1, and 4.[22] Leonhard Euler (1707–1783) advanced these ideas in the 18th century, introducing the term "quadratic residue" (Latin: residuum quadratica) in his 1754–1755 paper "Demonstratio theorematis Fermattiani omnium numerorum primorum formae $4n+1 in quadraticas primarias resolvi posse." Euler formalized properties of quadratic residues modulo primes, proving in 1749 that if a and b are coprime integers, then a^2 + b^2 has no prime divisor congruent to $3 \pmod{4}, linking sums of squares to residue classes. He developed Euler's criterion (discovered around 1748): for odd prime p and a not divisible by p, a is a quadratic residue modulo p if and only if a^{(p-1)/2} \equiv 1 \pmod{p}. Euler also computed explicit lists of quadratic residues for small primes, such as modulo 7 (0, 1, 2, 4), emphasizing their role in number-theoretic patterns without a general reciprocity law.[23][24] Joseph-Louis Lagrange (1736–1813) contributed in 1770 with his four-square theorem, proving that every natural number is the sum of four integer squares, published in Nouveaux mémoires de l'Académie royale des sciences et belles lettres de Berlin. This result extended Fermat's two-square theorem and provided further insights into sums of squares, though Lagrange focused more on integer representations than modular criteria. His work highlighted isolated facts, like the residues modulo small composites, bridging elementary observations toward deeper theory.Formulation of Quadratic Reciprocity
The law of quadratic reciprocity emerged in the late 18th and early 19th centuries as a pivotal advancement in number theory, building on earlier efforts to understand quadratic residues modulo primes. Adrien-Marie Legendre made significant partial contributions in 1785 through his paper Recherches d'analyse indéterminée, where he stated a version of the reciprocity law for distinct odd primes p and q, but his attempted proof was incomplete and covered only certain cases, failing to address all scenarios rigorously.[25] Carl Friedrich Gauss independently discovered and proved the full law in 1796 at the age of 19, though he delayed publication until 1801 in his seminal work Disquisitiones Arithmeticae, which integrated the concept of quadratic residues into a comprehensive framework for arithmetic.[26][27] In this text, Gauss formulated the law for distinct odd primes p and q as \left( \frac{p}{q} \right) \left( \frac{q}{p} \right) = (-1)^{\frac{p-1}{2} \cdot \frac{q-1}{2}}, where \left( \frac{\cdot}{\cdot} \right) denotes the Legendre symbol, and he provided the first two proofs, later developing six more distinct proofs over his career—eight in total—demonstrating his deep commitment to the theorem he called the "fundamental theorem" in the doctrine of residues.[28] Gauss also established the supplementary laws: for an odd prime p, \left( \frac{2}{p} \right) = (-1)^{\frac{p^2 - 1}{8}}, \quad \left( \frac{-1}{p} \right) = (-1)^{\frac{p-1}{2}}. These formulations completed the criteria for determining whether one prime is a quadratic residue modulo another. In the 1840s, Gotthold Eisenstein contributed elegant geometric proofs that simplified Gauss's third proof, offering more intuitive visualizations using lattice points and avoiding some technical complexities, as detailed in his 1845 exposition.[29][30] The publication of these results in Disquisitiones Arithmeticae and subsequent works revolutionized the field, enabling efficient computation of Legendre symbols without exhaustive trial, thus facilitating broader applications in number theory.[27]Distribution and Analytic Aspects
Counting Quadratic Residues
For an odd prime p, the multiplicative group (\mathbb{Z}/p\mathbb{Z})^* has order p-1, and the image of the squaring map on this group consists of exactly (p-1)/2 nonzero quadratic residues, since the map is 2-to-1 onto its image. Including 0, which is always a quadratic residue (as $0^2 \equiv 0 \pmod{p}), the total number of quadratic residues modulo p is (p+1)/2. This count holds because exactly half of the nonzero residues modulo p are squares, a consequence of the cyclic structure of (\mathbb{Z}/p\mathbb{Z})^*, where the subgroup of squares has index 2. As p varies over odd primes, approximately half of the elements in \{0, 1, \dots, p-1\} are quadratic residues, reflecting the balanced distribution in the cyclic group. In the integers \mathbb{Z}, the set of all quadratic residues (perfect squares) has natural density 0, since the number of such residues up to x is at most \sqrt{x} + 1 = O(\sqrt{x}).[12] For general n > 1, the number of quadratic residues modulo n is multiplicative and can be computed as the product of the numbers modulo the prime power factors of n, by the Chinese Remainder Theorem: an integer a is a quadratic residue modulo n if and only if it is a quadratic residue modulo each prime power dividing n. For n = p^k with p an odd prime, there are \phi(p^k)/2 = p^{k-1}(p-1)/2 quadratic residues coprime to p, plus additional residues divisible by p whose p-adic valuations are even and satisfy quadratic residue conditions modulo lower powers; a closed-form expression for the total in this case, as well as for powers of 2, is given by Stangl (1996).[31] For square-free n, the quadratic residues coprime to n number \phi(n)/2^{\omega(n)}, where \omega(n) is the number of distinct prime factors of n, so the proportion in (\mathbb{Z}/n\mathbb{Z})^* is $2^{-\omega(n)}, which is $1/2 when n is prime and decreases with more prime factors.[31] As an illustration, the quadratic residues modulo 12 (where $12 = 2^2 \times 3) are $0, 1, 4, 9, totaling 4 out of 12 elements.[32]Quadratic Reciprocity Law
The law of quadratic reciprocity provides a fundamental relation between the Legendre symbols \left( \frac{p}{q} \right) and \left( \frac{q}{p} \right) for distinct odd primes p and q. It states that \left( \frac{p}{q} \right) \left( \frac{q}{p} \right) = (-1)^{\frac{p-1}{2} \cdot \frac{q-1}{2}}. [33] This equality holds because the exponent \frac{p-1}{2} \cdot \frac{q-1}{2} is even when at least one of p or q is congruent to 1 modulo 4, making the symbols equal, and odd otherwise, making them negatives of each other.[34] Two supplementary laws extend the reciprocity to the cases of -1 and 2. For an odd prime p, \left( \frac{-1}{p} \right) = (-1)^{\frac{p-1}{2}}, which equals 1 if p \equiv 1 \pmod{4} and -1 if p \equiv 3 \pmod{4}.[33] Similarly, \left( \frac{2}{p} \right) = (-1)^{\frac{p^2 - 1}{8}}, which equals 1 if p \equiv \pm 1 \pmod{8} and -1 if p \equiv \pm 3 \pmod{8}.[35] These laws enable an efficient algorithm to compute the Legendre symbol \left( \frac{a}{p} \right) for odd prime p and integer a not divisible by p. First, reduce a modulo p to obtain $0 < b < p. If b = 0, the symbol is 0; otherwise, factor out squares from b (which do not change the symbol) until reaching a square-free kernel. Then, apply the supplementary laws if the kernel is -1 or 2 times an odd integer. For an odd prime factor q of the kernel, use reciprocity to swap: \left( \frac{q}{p} \right) = \left( \frac{p}{q} \right) (-1)^{\frac{p-1}{2} \cdot \frac{q-1}{2}}, reducing to a smaller denominator, and recurse until the denominator is small enough to evaluate directly (e.g., by checking if the numerator is a square modulo the small prime).[34] For example, to determine if 3 is a quadratic residue modulo 11, compute \left( \frac{3}{11} \right). Both 3 and 11 are odd primes congruent to 3 modulo 4, so the exponent \frac{3-1}{2} \cdot \frac{11-1}{2} = 1 \cdot 5 = 5 is odd. Thus, \left( \frac{3}{11} \right) = -\left( \frac{11}{3} \right). Now, $11 \equiv 2 \pmod{3}, so \left( \frac{11}{3} \right) = \left( \frac{2}{3} \right). Using the supplementary law, \left( \frac{2}{3} \right) = (-1)^{\frac{9-1}{8}} = (-1)^1 = -1. Therefore, \left( \frac{3}{11} \right) = -(-1) = 1, confirming 3 is a quadratic residue modulo 11.[34] Proofs of quadratic reciprocity typically rely on advanced techniques. An elementary proof uses induction on the primes combined with Gauss's lemma, which counts the number of negative residues in certain arithmetic progressions to evaluate the symbol.[33] Alternatively, Eisenstein's geometric proof interprets the symbol via lattice points in a circle, showing the reciprocity through area counts and symmetries.[34] A more analytic approach employs Gauss sums, defined as G = \sum_{k=1}^{p-1} \left( \frac{k}{p} \right) e^{2\pi i k / p}, whose magnitude squared equals p and whose evaluation leads to the reciprocity relation via properties of these sums over finite fields; full details appear in advanced texts.[33] The quadratic reciprocity law generalizes to the Jacobi symbol \left( \frac{a}{n} \right), defined for odd positive integer n > 1 and integer a coprime to n as the product of Legendre symbols over the prime factors of n. For distinct odd positive coprime integers m and n, the same reciprocity formula holds: \left( \frac{m}{n} \right) \left( \frac{n}{m} \right) = (-1)^{\frac{m-1}{2} \cdot \frac{n-1}{2}}, along with analogous supplementary laws for -1 and 2, allowing efficient computation without factoring n. Note that the Jacobi symbol equals 1 does not imply a is a quadratic residue modulo n, but equals -1 does imply it is not.[34]Character Sums and Bounds
Character sums involving the quadratic character provide powerful analytic tools for investigating the distribution of quadratic residues modulo a prime p. The quadratic Gauss sum, a central object in this context, is defined as S(h) = \sum_{k=1}^{p-1} \left( \frac{k}{p} \right) e^{2\pi i k h / p}, where \left( \frac{\cdot}{p} \right) denotes the Legendre symbol. For h \not\equiv 0 \pmod{p}, the magnitude satisfies |S(h)| = \sqrt{p}. This exact evaluation, first established by Gauss and extended in modern treatments, underpins many estimates on residue patterns and enables the derivation of explicit formulas for related L-functions.[36] Incomplete character sums, which truncate the full sum over a residue system, reveal the statistical behavior of quadratic residues. The Pólya–Vinogradov inequality offers a key bound: for any non-principal Dirichlet character \chi modulo q and positive integer N, \left| \sum_{n=1}^N \chi(n) \right| \ll \sqrt{q} \log q. When applied to the quadratic character \chi(n) = \left( \frac{n}{p} \right) modulo an odd prime p, this inequality controls the oscillation of partial sums and implies non-trivial limits on how residues deviate from uniformity.[37] These bounds directly inform the distribution of quadratic residues in short intervals. For instance, the number of quadratic residues modulo p in an interval [1, N] (with N < p) is \frac{N}{2} + O(\sqrt{p} \log p), measuring the discrepancy from the expected uniform proportion of \frac{1}{2}. Similar error terms arise in more general arithmetic progressions or intervals of length proportional to \sqrt{p}, where the Pólya–Vinogradov estimate ensures the residues are asymptotically balanced, up to the specified error. This has implications for detecting patterns in residue sequences and approximating the indicator function of residues via Fourier analysis.[38] Dirichlet introduced trigonometric expressions for the Legendre symbol, providing a bridge to analytic continuations. One such formula relates weighted sums involving the symbol to cotangent terms, as in \sum_{k=1}^{p-1} \left( \frac{k}{p} \right) k = -\sqrt{p} \sum_{k=1}^{p-1} \left( \frac{k}{p} \right) \cot\left( \frac{\pi k}{p} \right) for primes p \equiv 3 \pmod{4}, with analogous hyperbolic forms using logarithms of sines for broader evaluations. These representations, though intricate, facilitate derivations of special values in number theory, such as class numbers, while keeping the focus on finite sums for computational insight.[39] Overall, character sums and their bounds quantify error terms in the distribution of quadratic residues, ensuring that deviations from randomness remain controlled by \sqrt{p} \log p in typical settings. This framework extends to incomplete sums over arbitrary ranges, where the error in approximating the residue count by \frac{1}{2} times the interval length is governed by the same order, enabling precise asymptotic analyses without relying on deeper conjectures like the Riemann Hypothesis for quadratic characters.[37]Least Quadratic Non-Residue
In number theory, for an odd prime p, the least quadratic non-residue modulo p is defined as the smallest positive integer g such that the Legendre symbol \left( \frac{g}{p} \right) = -1.[40] This g is always a prime number, since any composite quadratic non-residue would imply a smaller prime non-residue as a factor.[41] Representative examples illustrate this concept: for p = 7, the quadratic residues modulo 7 are 0, 1, 2, and 4, so the least non-residue is g = 3; for p = 11, the residues are 0, 1, 3, 4, 5, and 9, yielding g = 2; similarly, for p = 13, the residues are 0, 1, 3, 4, 9, 10, and 12, again with g = 2.[40] Unconditionally, the best known upper bound on g is due to D. A. Burgess, who proved in 1957 that g = O\left( p^{1/(4\sqrt{e}) + \epsilon} \right) for any \epsilon > 0, where $1/(4\sqrt{e}) \approx 0.1516; this improves upon I. M. Vinogradov's earlier 1919 result of O\left( p^{1/\sqrt{e} + \epsilon} \right) with $1/\sqrt{e} \approx 0.6065.[42] Burgess's bound relies on estimates for short Dirichlet character sums modulo p, amplifying trivial bounds via the completion method.[43] Under the Generalized Riemann Hypothesis (GRH), stronger conditional bounds exist. N. C. Ankeny showed in 1952 that g \ll (\log p)^2 \log \log p, later refined by E. Bach in 1990 to the explicit form g < 2 (\log p)^2 for all odd primes p, and further to g \leq (\log p)^2 by Y. Lamzouri, X. Li, and K. Soundararajan in 2015.[44] These GRH bounds highlight the expected logarithmic scale of g, contrasting with the subpolynomial growth under the hypothesis. The least quadratic non-residue is connected to Artin's conjecture on primitive roots, as every primitive root modulo p must be a quadratic non-residue (since the quadratic residues form a proper subgroup of index 2 in (\mathbb{Z}/p\mathbb{Z})^\times), implying that the least primitive root is at least g. Under GRH, both quantities are bounded by O((\log p)^2), and C. Hooley's 1967 proof of Artin's conjecture relies on similar analytic techniques involving L-functions.[45]Quadratic Excess
The quadratic excess provides a measure of the imbalance in the distribution of quadratic residues and non-residues within short intervals modulo an odd prime p. For an interval [1, N] with $1 \leq N < p, it is defined as the absolute difference E = |R - NR|, where R is the number of quadratic residues in the interval and NR is the number of quadratic non-residues, so that R + NR = N. This quantity can be expressed precisely as E = \left| \sum_{k=1}^N \left( \frac{k}{p} \right) \right|, where \left( \frac{\cdot}{p} \right) denotes the Legendre symbol.[46] Davenport established results on the typical size of this excess across different intervals. Specifically, the average excess over all intervals of fixed length N is small, with the root-mean-square value bounded by O(\sqrt{N}), reflecting the expected random-like behavior of the Legendre symbol in short segments. For a uniform bound applicable to any single interval, the Pólya–Vinogradov inequality yields E = O(\sqrt{p \log p}), ensuring the deviation does not exceed this order regardless of N.[47][38] The quadratic excess is intrinsically linked to incomplete sums of the quadratic character \left( \frac{\cdot}{p} \right), as the expression above shows; bounds on such sums, including those from the Pólya–Vinogradov inequality, directly control the excess and reveal deviations from uniformity in residue distribution. These estimates relate to broader character sum techniques, such as the Pólya–Vinogradov result, which provides non-trivial bounds on partial sums of non-principal characters.[47] Studies of quadratic excess aid in sieve theory by quantifying local density imbalances of residues, which helps refine sifting processes for sets defined by quadratic conditions and improves estimates of residue patterns in arithmetic progressions or related structures.[38] For illustration, consider the interval [1, \lfloor p/2 \rfloor], where the excess is the classical quadratic excess E(p). For p=7, the quadratic residues modulo 7 are 1, 2, and 4; in [1,3], there are 2 residues (1,2) and 1 non-residue (3), so E=1. For p=11, residues are 1, 3, 4, 5, and 9; in [1,5], there are 4 residues (1,3,4,5) and 1 non-residue (2), so E=3. For p=13, residues are 1, 3, 4, 9, 10, and 12; in [1,6], there are 3 residues (1,3,4) and 3 non-residues, so E=0.Computational Methods
Square Roots Modulo Primes and Prime Powers
Computing square roots modulo an odd prime p, where the input a is a quadratic residue modulo p, can be done efficiently using specialized algorithms. For primes p \equiv 3 \pmod{4}, a simple and direct method exists: the square roots are given by \pm a^{(p+1)/4} \pmod{p}. This formula arises from properties of the multiplicative group modulo p and Euler's criterion, and it requires only a single modular exponentiation.[48] For the general case of odd primes p \equiv 1 \pmod{4}, or more broadly for any odd prime, the Tonelli-Shanks algorithm provides a systematic approach to extract the roots. Developed by building on earlier work, the algorithm proceeds as follows: first, factor p-1 = 2^s q where q is odd; then, identify a quadratic non-residue z modulo p (e.g., by testing small values until the Legendre symbol (z/p) = -1); set c = z^q \pmod{p}, r = a^{(q+1)/2} \pmod{p}, and t = a^q \pmod{p}; iteratively adjust r and t over s-1 steps by finding the smallest i such that t^{2^i} \equiv 1 \pmod{p}, computing a correction factor b = c^{2^{s-i-1}} \pmod{p}, and updating r \leftarrow r b \pmod{p} and t \leftarrow t b^2 \pmod{p}. The final r satisfies r^2 \equiv a \pmod{p}, and the other root is -r \pmod{p}. This method relies on discrete logarithm-like steps within the 2-Sylow subgroup of the multiplicative group.[48] (Note: Direct link to Shanks' original proceedings unavailable; cited via standard reference.) For the prime p = 2, the cases are straightforward and trivial for small powers. Modulo 2, the quadratic residues are 0 and 1, with roots 0 and 1 (or -1 ≡ 1). Modulo 4, the residues are 0 and 1, with roots \pm 0 \equiv 0 and \pm 1 \equiv 1,3. Modulo 8, the residues are 0, 1, and 4, with roots 0 for 0, \pm 1 \equiv 1,7 for 1, and \pm 2 \equiv 2,6 for 4. Higher powers of 2 require lifting, as detailed below.[48] To extend solutions from modulo p to modulo p^k for k > 1, Hensel's lemma provides an iterative lifting procedure, applicable when the derivative condition holds. Suppose x_0^2 \equiv a \pmod{p} with $2x_0 \not\equiv [0](/page/0) \pmod{p} (true for odd p and nonzero residues). Define f(x) = x^2 - a; then, for each step from m to m+1 (up to k), solve x_{m+1} = x_m - f(x_m) \cdot (f'(x_m))^{-1} \pmod{p^{m+1}}, where f'(x) = 2x and the inverse exists modulo p by the initial condition. This Newton-Raphson-like iteration converges quadratically, lifting the root uniquely under the nonsingularity assumption. For p=2 and k \geq 3, lifting starts from modulo 8 solutions, but requires care since f'(x_0) \equiv [0](/page/0) \pmod{2}; in such cases, multiple lifts (up to four for odd residues) are possible, and the process adjusts for higher valuation.[49] As an example, consider computing a square root of 4 modulo 7 (p=7 \equiv [3](/page/3) \pmod{4}): $4^{(7+1)/4} = 4^2 = 16 \equiv 2 \pmod{7}, and the roots are \pm 2 \equiv 2,5 \pmod{7}, since $2^2 = 4 and $5^2 = 25 \equiv 4 \pmod{7}. For lifting to modulo 9 (p=[3](/page/3), k=2): start with \sqrt{1} \equiv 1 \pmod{3}; then x_1 = 1 - (1^2 - 1) \cdot (2 \cdot 1)^{-1} \equiv 1 \pmod{9} (trivially, since exact), but checking, roots are 1 and 8 modulo 9, as $8^2 = 64 \equiv 1 \pmod{9}; the other lift from -1 \equiv 2 \pmod{3} yields 8.[48] The Tonelli-Shanks algorithm runs in O(\log^2 p) time using fast exponentiation for the modular operations, assuming a quadratic non-residue is found efficiently (e.g., in expected O(\log p) trials). The simple case for p \equiv 3 \pmod{4} is faster at O(\log p) exponentiations. Lifting via Hensel's lemma requires O(\log k \cdot \log p) steps, each with modular arithmetic of size O(p^k), but for fixed k or using fast methods, it remains polynomial in \log p.[48]Square Roots Modulo Composites
When the prime factorization of a composite modulus n = \prod p_i^{k_i} is known, square roots of a quadratic residue a modulo n can be computed by first finding the square roots modulo each prime power factor p_i^{k_i} and then combining them using the Chinese Remainder Theorem (CRT).[50] Methods for computing square roots modulo prime powers, such as Tonelli-Shanks for odd primes or explicit formulas for powers of 2, are applied separately to each component.[51] The CRT then lifts these local solutions to global solutions modulo n, as the rings \mathbb{Z}/p_i^{k_i}\mathbb{Z} are pairwise coprime.[52] For example, consider solving x^2 \equiv 4 \pmod{15}, where n=15=3 \times 5. Modulo 3, $4 \equiv 1 \pmod{3}, so the roots are x \equiv \pm 1 \pmod{3} (i.e., 1 and 2). Modulo 5, $4 \equiv 4 \pmod{5}, so the roots are x \equiv \pm 2 \pmod{5} (i.e., 2 and 3). The four combinations are then solved via CRT:- x \equiv 1 \pmod{3}, x \equiv 2 \pmod{5} yields x \equiv 7 \pmod{15};
- x \equiv 1 \pmod{3}, x \equiv 3 \pmod{5} yields x \equiv 13 \pmod{15};
- x \equiv 2 \pmod{3}, x \equiv 2 \pmod{5} yields x \equiv 2 \pmod{15};
- x \equiv 2 \pmod{3}, x \equiv 3 \pmod{5} yields x \equiv 8 \pmod{15}.
All satisfy x^2 \equiv 4 \pmod{15}.[51]
Complexity Considerations
Determining quadratic residuosity modulo a prime p is computationally efficient. Euler's criterion states that a is a quadratic residue modulo p if and only if a^{(p-1)/2} \equiv 1 \pmod{p}, which can be verified using modular exponentiation in O(\log p) arithmetic operations assuming constant-time multiplication.[3] Alternatively, the Legendre symbol (a/p) can be computed in O(\log p) time via the law of quadratic reciprocity, reducing the problem to a series of simpler evaluations.[3] Finding square roots modulo a prime is also feasible in polynomial time. The deterministic Tonelli-Shanks algorithm computes such roots for odd primes in O(\log^2 p) time, relying on exponentiations and a search for a quadratic non-residue.[55] Probabilistic variants, such as randomized selections in extensions of Tonelli-Shanks, achieve expected running times faster than O(\log^2 p) under certain conditions, though deterministic guarantees remain O(\log^2 p).[55] Modulo a composite n, the situation changes dramatically. Deciding quadratic residuosity for a with Jacobi symbol (a/n) = 1 is believed to be computationally hard, with no known polynomial-time algorithm without the factorization of n; this forms the quadratic residuosity assumption underlying several cryptographic primitives.[56] Computing square roots modulo n is equivalent in hardness to integer factorization: an oracle for square roots allows factoring n in polynomial time by exploiting the four possible roots and gcd computations, and conversely, roots can be found efficiently once factors are known via the Chinese Remainder Theorem.[57] Quantum computing alters this landscape. Shor's algorithm factors composite integers in polynomial time on a quantum computer, thereby enabling efficient solution of both residuosity testing and square root extraction modulo composites by first obtaining the prime factors. Space and time tradeoffs arise in related factoring tasks. For instance, Berlekamp's algorithm for factoring polynomials over finite fields \mathbb{F}_p leverages computations of quadratic residues and non-residues (via algorithms like Tonelli-Shanks) to identify irreducible factors, balancing probabilistic root-finding steps against deterministic verification for overall polynomial-time performance.[58] Under standard cryptographic assumptions, such as the hardness of factoring, no efficient classical algorithm exists for square root finding or residuosity testing modulo composites without factorization, establishing conditional lower bounds of superpolynomial time.[56][57]Applications
Primality Testing and Factorization
Quadratic residues play a central role in probabilistic primality testing through algorithms that leverage Euler's criterion, which states that for a prime p and integer a not divisible by p, a^{(p-1)/2} \equiv \left( \frac{a}{p} \right) \pmod{p}, where \left( \frac{a}{p} \right) is the Legendre symbol indicating quadratic residuosity. The Solovay-Strassen test, introduced in 1977, extends this to composite moduli using the Jacobi symbol \left( \frac{a}{n} \right) in place of the Legendre symbol; for a candidate prime n, it selects random bases a coprime to n and verifies whether \left( \frac{a}{n} \right) \equiv a^{(n-1)/2} \pmod{n}. If the equality fails for any a, n is composite; if it holds for k independent random a, the probability that a composite n passes is at most $1/2^k. This test efficiently detects compositeness by exploiting mismatches in quadratic residuosity properties, with each trial requiring computation of the Jacobi symbol and modular exponentiation. The Miller-Rabin primality test, developed in the late 1970s and early 1980s, builds on similar principles but focuses on strong pseudoprimes rather than direct quadratic residuosity checks, avoiding the need for Jacobi symbol computations by testing stronger conditions derived from the same Euler criterion framework. While Solovay-Strassen relies explicitly on quadratic symbols to witness compositeness, Miller-Rabin uses iterative squaring to check if a^{2^s d} \equiv \pm 1 \pmod{n} for decomposed exponents, where failures indicate non-residuosity-like behavior signaling compositeness. This relation highlights how quadratic residue concepts underpin both tests, though Miller-Rabin's emphasis on strong witnesses makes it faster and more widely implemented in practice. In integer factorization, quadratic residues facilitate sieving techniques in methods like Dixon's algorithm and the quadratic sieve, where they help identify smooth values modulo small primes to construct relations for factoring. Dixon's method, proposed in 1981, generates random squares x_i^2 \pmod{n} and sieves for partial smoothness by checking quadratic residuosity modulo a factor base of small primes, retaining those x_i^2 - n that factor completely over the base to form a matrix whose kernel yields nontrivial factors of n. The quadratic sieve, refined by Pomerance in 1984, improves this by evaluating a quadratic polynomial (x + \lfloor \sqrt{n} \rfloor )^2 - n over a sieving interval, using Legendre symbols \left( \frac{f(p)}{p} \right) for small primes p in the factor base to locate candidate smooth values efficiently, leading to relations that solve for factors via linear algebra. These approaches exploit the density of quadratic residues (roughly half the nonzero residues modulo a prime) to accelerate the search for smooth differences of squares.[59] The continued fraction factorization algorithm (CFRAC), advanced as a computational method in 1975, also incorporates quadratic residuosity in generating and verifying relations from approximations to \sqrt{n}. It derives convergents from the continued fraction expansion of \sqrt{n}, yielding equations of the form x^2 - k n = y^2 for small k, and sieves the left-hand sides for smoothness by testing residuosity modulo factor base primes to confirm factorizations, accumulating relations until a dependency reveals a factor of n. In all these factoring methods, quadratic residuosity serves as a sieve to eliminate non-smooth candidates quickly, enhancing efficiency for large n. More broadly, in primality contexts, a failure of \left( \frac{a}{n} \right) \not\equiv a^{(n-1)/2} \pmod{n} for composite n and coprime a directly proves compositeness, as this congruence holds universally for primes by Euler's criterion.Cryptography
The Rabin cryptosystem, introduced by Michael O. Rabin in 1979, is a public-key encryption scheme that leverages the computational difficulty of extracting square roots modulo a composite number. In this system, the public key consists of a modulus n = pq where p and q are large distinct primes congruent to 3 modulo 4, and encryption of a plaintext message m (padded with redundancy to disambiguate roots) is performed by computing the ciphertext c = m^2 \mod n. Decryption involves computing the four possible square roots modulo n using the Chinese Remainder Theorem after finding roots modulo p and q separately, which requires knowledge of the private factors; the redundancy ensures the correct root can be identified probabilistically with high probability.[60] The security of the Rabin cryptosystem is equivalent to the hardness of integer factorization, as an oracle for decryption would allow efficient factoring. The quadratic residuosity assumption posits that, given a composite modulus n = pq with p and q large primes, it is computationally infeasible to distinguish quadratic residues from non-residues modulo n without knowing the factors. This assumption underpins several cryptographic primitives, including the Goldwasser-Micali cryptosystem proposed in 1982, which achieves semantic security by encrypting each bit of the message using random quadratic residues or non-residues modulo n, with the Legendre symbol determining the bit value during decryption. Building on similar ideas, the Blum-Goldwasser cryptosystem from 1985 provides probabilistic encryption for multi-bit messages by generating a pseudorandom bit stream via iterated squaring in the subgroup of quadratic residues modulo n (using primes p, q \equiv 3 \mod 4), which is XORed with the plaintext; security relies on the intractability of predicting the least significant bits of such iterates, tied to the quadratic residuosity problem. The Okamoto-Uchiyama cryptosystem, introduced in 1998, extends these concepts to higher powers by using a modulus n = p^2 q where p is a large prime and q is another prime, focusing on the difficulty of deciding membership in the subgroup of order p. Encryption maps a message m (in the range 0 to p-1) to c = g^m \cdot h^r \pmod{n} for a base g of order p modulo p^2, public h = g^p \pmod{n}, and random r, allowing decryption via the private key p but remaining secure under the decisional p-th residuosity assumption without it. For digital signatures, schemes based on the quadratic residuosity assumption include the Goldwasser-Micali-Rivest construction from 1988, which uses zero-knowledge proofs of residuosity (inspired by earlier work on interactive proofs) combined with the Fiat-Shamir heuristic to produce signatures robust against adaptive chosen-message attacks, with security reducible to the assumption. Despite their provable security foundations, these quadratic residue-based systems face significant post-quantum threats, as Shor's algorithm enables efficient quantum solution of the integer factorization problem, breaking the underlying hardness assumptions for Rabin, Goldwasser-Micali, Blum-Goldwasser, and related schemes. The Okamoto-Uchiyama scheme is similarly vulnerable due to its reliance on factorization modulo prime powers. Efforts to adapt these for post-quantum settings have been limited, with most focus shifting to lattice-based or hash-based alternatives.[61]Other Fields
In acoustics, quadratic residue diffusers are structures designed to scatter sound waves evenly in rooms, such as concert halls, by using sequences derived from quadratic residues modulo a prime number. These diffusers, pioneered by Manfred R. Schroeder in 1975, consist of wells or panels whose depths follow a quadratic residue sequence, ensuring uniform diffusion across a wide frequency range while minimizing specular reflections. For example, a prime like 7 yields the sequence 0, 1, 4, 2 (corresponding to the quadratic residues modulo 7), which determines the well depths to achieve effective sound scattering. In graph theory, quadratic residues form the basis for Paley graphs, which are constructed over the finite field \mathbb{F}_q where q is a prime power congruent to 1 modulo 4; the vertices are the field elements, and an edge connects x and y if x - y is a nonzero quadratic residue. Introduced by Raymond Paley in 1933 as part of his work on orthogonal matrices, these graphs are strongly regular, meaning they have constant degrees and uniform adjacency properties among non-adjacent vertices, which facilitates their analysis in extremal graph theory. Paley graphs also appear in coding theory due to their symmetric structure and connection to Hadamard matrices. Quadratic residue codes represent a class of cyclic error-correcting codes defined over finite fields, where the generator polynomial's roots correspond to quadratic residues modulo a prime p. For binary codes with length p \equiv 3 \pmod{4}, these codes are constructed by evaluating the quadratic residues to form the code's parity-check matrix, yielding self-dual codes with good minimum distance properties; notable examples include the binary Golay code of length 23, which corrects up to 3 errors. Such codes, studied extensively since the 1960s, are applied in data transmission for their efficiency in detecting and correcting errors without excessive redundancy.[62] In combinatorics and statistics, quadratic residues underpin the construction of Paley tournaments and related designs, where for a prime q \equiv 3 \pmod{4}, the tournament directs an edge from x to y in \mathbb{Z}/q\mathbb{Z} if y - x is a quadratic residue, producing a regular tournament with balanced out-degrees. These structures support combinatorial designs, such as difference sets, where the set of quadratic residues modulo p forms a (p, (p-1)/2, (p-5)/4)-difference set, enabling the creation of balanced incomplete block designs used in experimental design and statistical modeling. Additionally, random walks on graphs defined by quadratic residue adjacencies, like Paley graphs, model diffusion processes and exhibit spectral properties tied to the distribution of residues, aiding analysis in probabilistic combinatorics.[63][64]Examples and Tables
Small Moduli Examples
The only nonzero residue class coprime to 2 is 1, which is a quadratic residue since $1^2 \equiv 1 \pmod{2}.[6] Modulo 3, the quadratic residues are 1, obtained from $1^2 \equiv 1 \pmod{3} and $2^2 \equiv 1 \pmod{3}, while 2 is a non-residue.[3] For modulus 4, the nonzero residues coprime to 4 are 1 and 3. The quadratic residue is 1, as $1^2 \equiv 1 \pmod{4} and $3^2 \equiv 1 \pmod{4}; 3 is a non-residue. (Note: squares modulo 4 are 0 and 1, but only coprime nonzero a qualify as quadratic residues per the definition.)[65] Modulo 5, the quadratic residues are 1 and 4, computed from the nonzero squares $1^2 \equiv 1, $2^2 \equiv 4, $3^2 \equiv 4, and $4^2 \equiv 1 \pmod{5}; the non-residues are 2 and 3.[6] This can be verified using the Legendre symbol, where \left( \frac{2}{5} \right) = -1, confirming that 2 is a non-residue modulo 5.[3] For modulus 7, the quadratic residues are 1, 2, and 4, arising from $1^2 \equiv 1, $2^2 \equiv 4, $3^2 \equiv 2, $4^2 \equiv 2, $5^2 \equiv 4, and $6^2 \equiv 1 \pmod{7}; the non-residues are 3, 5, and 6.[3] Modulo 11, a prime, the quadratic residues are 1, 3, 4, 5, and 9, with corresponding square roots as follows: 1 from \pm1^2 (1 and 10); 3 from \pm5^2 (5 and 6); 4 from \pm2^2 (2 and 9); 5 from \pm4^2 (4 and 7); 9 from \pm3^2 (3 and 8). The non-residues are 2, 6, 7, 8, and 10.[6] For modulus 13, another prime, the quadratic residues are 1, 3, 4, 9, 10, and 12, with square roots: 1 from \pm1^2 (1 and 12); 3 from \pm4^2 (4 and 9); 4 from \pm2^2 (2 and 11); 9 from \pm3^2 (3 and 10); 10 from \pm6^2 (6 and 7); 12 from \pm5^2 (5 and 8). The non-residues are 2, 5, 6, 7, 8, and 11.[6] A notable pattern in these examples for prime moduli is the symmetry between residues x and p - x, since (p - x)^2 \equiv x^2 \pmod{p}, pairing square roots and producing symmetric residue sets.[3] Additionally, for odd primes p, there are exactly (p-1)/2 quadratic residues among the p-1 nonzero residue classes, yielding a density of exactly 1/2, as observed in the cases modulo 5 (2 out of 4), 7 (3 out of 6), 11 (5 out of 10), and 13 (6 out of 12).[6]Table of Quadratic Residues
The following table lists the nonzero quadratic residues (sorted in increasing order), the quadratic non-residues (the remaining nonzero residues coprime to p), and the least quadratic non-residue for odd primes p up to 31. Each nonzero quadratic residue modulo a prime p has exactly two square roots, which are additive inverses modulo p.[6][3]| Prime p | Nonzero Quadratic Residues | Quadratic Non-Residues | Least Non-Residue |
|---|---|---|---|
| 3 | 1 | 2 | 2 |
| 5 | 1, 4 | 2, 3 | 2 |
| 7 | 1, 2, 4 | 3, 5, 6 | 3 |
| 11 | 1, 3, 4, 5, 9 | 2, 6, 7, 8, 10 | 2 |
| 13 | 1, 3, 4, 9, 10, 12 | 2, 5, 6, 7, 8, 11 | 2 |
| 17 | 1, 2, 4, 8, 9, 13, 15, 16 | 3, 5, 6, 7, 10, 11, 12, 14 | 3 |
| 19 | 1, 4, 5, 6, 7, 9, 11, 16, 17 | 2, 3, 8, 10, 12, 13, 14, 15, 18 | 2 |
| 23 | 1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18 | 5, 7, 10, 11, 14, 15, 19, 20, 21, 22 | 5 |
| 29 | 1, 4, 5, 6, 7, 9, 13, 16, 20, 22, 23, 24, 25, 28 | 2, 3, 8, 10, 11, 12, 14, 15, 17, 18, 19, 21, 26, 27 | 2 |
| 31 | 1, 2, 4, 5, 7, 8, 9, 10, 14, 15, 16, 18, 19, 20, 25, 28 | 3, 6, 11, 12, 13, 17, 21, 22, 23, 24, 26, 27, 29, 30 | 3 |
| Modulus n | Nonzero Coprime Quadratic Residues |
|---|---|
| 6 | 1 |
| 8 | 1 |
| 9 | 1, 4, 7 |
| 10 | 1, 9 |
| 12 | 1 |
| 15 | 1, 4 |