Quadratic residue

In number theory, an integer q is a quadratic residue modulo n if it is congruent to a perfect square modulo n; that is, if there exists an integer x such that

\(x^2\equiv q \pmod{n}.\)

Otherwise, q is a quadratic nonresidue modulo n.

Quadratic residues are used in applications ranging from acoustical engineering to cryptography and the factoring of large numbers.

Fermat, Euler, Lagrange, Legendre, and other number theorists of the 17th and 18th centuries established theorems and formed conjectures about quadratic residues, but the first systematic treatment is § IV of Gauss's Disquisitiones Arithmeticae (1801). Article 95 introduces the terminology "quadratic residue" and "quadratic nonresidue", and says that if the context makes it clear, the adjective "quadratic" may be dropped.

For a given n, a list of the quadratic residues modulo n may be obtained by simply squaring all the numbers 0, 1, ..., n − 1. Since a ≡ b (mod n) implies a≡b (mod n), any other quadratic residue is congruent (mod n) to some in the obtained list. But the obtained list is not composed of mutually incongruent quadratic residues (mod n) only. Since a≡(n−a) (mod n), the list obtained by squaring all numbers in the list 1, 2, ..., n − 1 (or in the list 0, 1, ..., n) is symmetric (mod n) around its midpoint, hence it is actually only needed to square all the numbers in the list \(0, 1, ..., \lfloor n/2 \rfloor\). The list so obtained may still contain mutually congruent numbers (mod n). Thus, the number of mutually noncongruent quadratic residues modulo n cannot exceed n/2 + 1 (n even) or (n + 1)/2 (n odd).

The product of two residues is always a residue.

Modulo an odd prime number p there are (p + 1)/2 residues (including 0) and (p − 1)/2 nonresidues, by Euler's criterion. In this case, it is customary to consider 0 as a special case and work within the multiplicative group of nonzero elements of the field \((\mathbb{Z}/p\mathbb{Z})\). In other words, every congruence class except zero modulo p has a multiplicative inverse. This is not true for composite moduli.

Following this convention, the multiplicative inverse of a residue is a residue, and the inverse of a nonresidue is a nonresidue.

Following this convention, modulo an odd prime number there is an equal number of residues and nonresidues.

Modulo a prime, the product of two nonresidues is a residue and the product of a nonresidue and a (nonzero) residue is a nonresidue.

The first supplement to the law of quadratic reciprocity is that if p ≡ 1 (mod 4) then −1 is a quadratic residue modulo p, and if p ≡ 3 (mod 4) then −1 is a nonresidue modulo p. This implies the following:

If p ≡ 1 (mod 4) the negative of a residue modulo p is a residue and the negative of a nonresidue is a nonresidue.

If p ≡ 3 (mod 4) the negative of a residue modulo p is a nonresidue and the negative of a nonresidue is a residue.

All odd squares are ≡ 1 (mod 8) and thus also ≡ 1 (mod 4). If a is an odd number and m = 8, 16, or some higher power of 2, then a is a residue modulo m if and only if a ≡ 1 (mod 8).

So a nonzero number is a residue mod 8, 16, etc., if and only if it is of the form 4(8n + 1).

A number a relatively prime to an odd prime p is a residue modulo any power of p if and only if it is a residue modulo p.

If the modulus is p,

then pa

is a residue modulo p if k ≥ n

is a nonresidue modulo p if k < n is odd

is a residue modulo p if k < n is even and a is a residue

is a nonresidue modulo p if k < n is even and a is a nonresidue.

Notice that the rules are different for powers of two and powers of odd primes.

Modulo an odd prime power n = p, the products of residues and nonresidues relatively prime to p obey the same rules as they do mod p; p is a nonresidue, and in general all the residues and nonresidues obey the same rules, except that the products will be zero if the power of p in the product ≥ n.

Modulo 8, the product of the nonresidues 3 and 5 is the nonresidue 7, and likewise for permutations of 3, 5 and 7. In fact, the multiplicative group of the non-residues and 1 form the Klein four-group.

The basic fact in this case is

if a is a residue modulo n, then a is a residue modulo p for every prime power dividing n.

if a is a nonresidue modulo n, then a is a nonresidue modulo p for at least one prime power dividing n.

Modulo a composite number, the product of two residues is a residue. The product of a residue and a nonresidue may be a residue, a nonresidue, or zero.

Also, the product of two nonresidues may be either a residue, a nonresidue, or zero.

This phenomenon can best be described using the vocabulary of abstract algebra. The congruence classes relatively prime to the modulus are a group under multiplication, called the group of units of the ring \((\mathbb{Z}/n\mathbb{Z})\), and the squares are a subgroup of it. Different nonresidues may belong to different cosets, and there is no simple rule that predicts which one their product will be in. Modulo a prime, there is only the subgroup of squares and a single coset.

The fact that, e.g., modulo 15 the product of the nonresidues 3 and 5, or of the nonresidue 5 and the residue 9, or the two residues 9 and 10 are all zero comes from working in the full ring \((\mathbb{Z}/n\mathbb{Z})\), which has zero divisors for composite n.

For this reason some authors add to the definition that a quadratic residue a must not only be a square but must also be relatively prime to the modulus n. (a is coprime to n if and only if a is coprime to n.)

Although it makes things tidier, this article does not insist that residues must be coprime to the modulus.

Gauss used R and N to denote residuosity and non-residuosity, respectively;

for example, 2 R 7 and 5 N 7, or 1 R 8 and 3 N 8.

Although this notation is compact and convenient for some purposes, a more useful notation is the Legendre symbol, also called the quadratic character, which is defined for all integers a and positive odd prime numbers p as

\(\left(\frac{a}{p}\right) = \begin{cases}\;\;\,0&\text{ if }p \text { divides } a\\+1&\text{ if } a \operatorname{R} p \text{ and }p \text { does not divide } a\\-1&\text{ if }a \operatorname{N} p \text{ and }p \text{ does not divide } a\end{cases}\)

There are two reasons why numbers ≡ 0 (mod p) are treated specially. As we have seen, it makes many formulas and theorems easier to state. The other (related) reason is that the quadratic character is a homomorphism from the multiplicative group of nonzero congruence classes modulo p to the complex numbers under multiplication. Setting \((\tfrac{np}{p}) = 0\) allows its domain to be extended to the multiplicative semigroup of all the integers.

One advantage of this notation over Gauss's is that the Legendre symbol is a function that can be used in formulas. It can also easily be generalized to cubic, quartic and higher power residues.

There is a generalization of the Legendre symbol for composite values of p, the Jacobi symbol, but its properties are not as simple: if m is composite and the Jacobi symbol \((\tfrac{a}{m}) = -1,\) then a N m, and if a R m then \((\tfrac{a}{m}) = 1,\) but if \((\tfrac{a}{m}) = 1\) we do not know whether a R m or a N m. For example: \((\tfrac{2}{15}) = 1\) and \((\tfrac{4}{15}) = 1\), but 2 N 15 and 4 R 15. If m is prime, the Jacobi and Legendre symbols agree.

Although quadratic residues appear to occur in a rather random pattern modulo n, and this has been exploited in such applications as acoustics and cryptography, their distribution also exhibits some striking regularities.

Using Dirichlet's theorem on primes in arithmetic progressions, the law of quadratic reciprocity, and the Chinese remainder theorem (CRT) it is easy to see that for any M > 0 there are primes p such that the numbers 1, 2, ..., M are all residues modulo p.

The first of these regularities stems from Peter Gustav Lejeune Dirichlet's work (in the 1830s) on the analytic formula for the class number of binary quadratic forms. Let q be a prime number, s a complex variable, and define a Dirichlet L-function as

\(L(s) = \sum_{n=1}^\infty\left(\frac{n}{q}\right)n^{-s}.\)

Dirichlet showed that if q ≡ 3 (mod 4), then

\(L(1) = -\frac{\pi}{\sqrt q}\sum_{n=1}^{q-1} \frac{n}{q} \left(\frac{n}{q}\right) > 0.\)

Therefore, in this case (prime q ≡ 3 (mod 4)), the sum of the quadratic residues minus the sum of the nonresidues in the range 1, 2, ..., q − 1 is a negative number.

In fact the difference will always be an odd multiple of q if q > 3. In contrast, for prime q ≡ 1 (mod 4), the sum of the quadratic residues minus the sum of the nonresidues in the range 1, 2, ..., q − 1 is zero, implying that both sums equal \(\frac{q(q-1)}{4}\).

Dirichlet also proved that for prime q ≡ 3 (mod 4),

\(L(1) = \frac{\pi}{\left(2-\left(\frac{2}{q}\right)\right)\!\sqrt q}\sum_{n=1}^\frac{q-1}{2}\left(\frac{n}{q}\right) > 0.\)

This implies that there are more quadratic residues than nonresidues among the numbers 1, 2, ..., (q − 1)/2.

An intriguing fact about these two theorems is that all known proofs rely on analysis; no-one has ever published a simple or direct proof of either statement.

If p and q are odd primes, then:

((p is a quadratic residue mod q) if and only if (q is a quadratic residue mod p)) if and only if (at least one of p and q is congruent to 1 mod 4).

That is:

\(\left(\frac{p}{q}\right) \left(\frac{q}{p}\right) = (-1)^{\frac{p-1}{2} \cdot \frac{q-1}{2}}\)

where \(\left(\frac{p}{q}\right)\) is the Legendre symbol.

Thus, for numbers a and odd primes p that don't divide a:

Modulo a prime p, the number of pairs n, n + 1 where n R p and n + 1 R p, or n N p and n + 1 R p, etc., are almost equal. More precisely, let p be an odd prime. For i, j = 0, 1 define the sets

\(A_{ij}=\left\{k\in\{1,2,\dots,p-2\}: \left(\frac{k}{p}\right)=(-1)^i\land\left(\frac{k+1}{p}\right)=(-1)^j\right\},\)

and let

\(\alpha_{ij} = |A_{ij}|.\)

That is,

α₀₀ is the number of residues that are followed by a residue,

α₀₁ is the number of residues that are followed by a nonresidue,

α₁₀ is the number of nonresidues that are followed by a residue, and

α₁₁ is the number of nonresidues that are followed by a nonresidue.

Then if p ≡ 1 (mod 4)

\(\alpha_{00} = \frac{p-5}{4},\;\alpha_{01} =\alpha_{10} =\alpha_{11} = \frac{p-1}{4}\)

and if p ≡ 3 (mod 4)

\(\alpha_{01} = \frac{p+1}{4},\;\alpha_{00} =\alpha_{10} =\alpha_{11} = \frac{p-3}{4}.\)

Gauss (1828) introduced this sort of counting when he proved that if p ≡ 1 (mod 4) then x ≡ 2 (mod p) can be solved if and only if p = a + 64 b.

The values of \((\tfrac{a}{p})\) for consecutive values of a mimic a random variable like a coin flip. Specifically, Pólya and Vinogradov proved (independently) in 1918 that for any nonprincipal Dirichlet character χ(n) modulo q and any integers M and N,

\(\left|\sum_{n=M+1}^{M+N}\chi(n)\right| =O\left( \sqrt q \log q\right),\)

in big O notation. Setting

\(\chi(n) = \left(\frac{n}{q}\right),\)

this shows that the number of quadratic residues modulo q in any interval of length N is

\(\frac{1}{2}N + O(\sqrt q\log q).\)

It is easy to prove that

\(\left| \sum_{n=M+1}^{M+N} \left( \frac{n}{q} \right) \right| < \sqrt q \log q.\)

In fact,

\(\left| \sum_{n=M+1}^{M+N} \left( \frac{n}{q} \right) \right| < \frac{4}{\pi^2} \sqrt q \log q+0.41\sqrt q +0.61.\)

Montgomery and Vaughan improved this in 1977, showing that, if the generalized Riemann hypothesis is true then

\(\left|\sum_{n=M+1}^{M+N}\chi(n)\right|=O\left(\sqrt q \log \log q\right).\)

This result cannot be substantially improved, for Schur had proved in 1918 that

\(\max_N \left|\sum_{n=1}^{N}\left(\frac{n}{q}\right)\right|>\frac{1}{2\pi}\sqrt q\)

\(\max_N \left|\sum_{n=1}^{N}\left(\frac{d}{n}\right)\right|>\frac{1}{7}\sqrt d \log \log d\)

Condensed: the full section is in Wikipedia.

The least quadratic residue mod p is clearly 1. The question of the magnitude of the least quadratic non-residue n(p) is more subtle, but it is always prime, with 7 appearing for the first time at 71.

The Pólya-Vinogradov inequality above gives O(√p log p).

The best unconditional estimate is n(p) ≪ p for any θ > ⁠1/4⁠√e, obtained by estimates of Burgess on character sums.

Assuming the Generalised Riemann hypothesis, Ankeny obtained n(p) ≪ (log p).

Linnik showed that the number of p less than X such that n(p) > X is bounded by a constant depending on ε.

The least quadratic non-residues mod p for odd primes p are:

2, 2, 3, 2, 2, 3, 2, 5, 2, 3, 2, ... (sequence A053760 in the OEIS)

Let p be an odd prime. The quadratic excess E(p) is the number of quadratic residues on the range (0,p/2) minus the number in the range (p/2,p) (sequence A178153 in the OEIS). For p congruent to 1 mod 4, the excess is zero, since −1 is a quadratic residue and the residues are symmetric under r ↔ p−r. For p congruent to 3 mod 4, the excess E is always positive.

Two natural computational problems are:

1. Given a number a and a modulus n, determine whether a is a quadratic residue.
2. Calculate a square root of a (that is, a solution to x ≡ a (mod n)), assuming one exists.

For prime moduli, both problems can be solved efficiently using the Tonelli-Shanks algorithm; the same is true for composite moduli whose prime factorization is known. In the case of a composite modulus with unknown prime factorization, the problem of identifying quadratic residues is known as the quadratic residuosity problem and is believed to be computationally difficult.

Modulo a prime p, a quadratic residue a has 1 + (a|p) roots (i.e. zero if a N p, one if a ≡ 0 (mod p), or two if a R p and gcd(a, p) = 1.)

In general, if a composite modulus n is written as a product of powers of distinct primes, and there are n₁ roots modulo the first one, n₂ mod the second, ..., there will be n₁n₂... roots modulo n.

The theoretical way solutions modulo the prime powers are combined to make solutions modulo n is called the Chinese remainder theorem; it can be implemented with an efficient algorithm.