Quadratic residue ($a\equiv x^2(\mathrm{mod}p)$)

For an odd prime $p$, a nonzero congruence class $a$ is a quadratic residue when $a\equiv x^2(\mathrm{mod}p)$ for some integer $x$. Here "quadratic residue" excludes zero: zero is a square of a number, but is neither a quadratic residue nor a quadratic nonresidue under this convention. Some treatments include zero among quadratic residues; the distinction matters when counting them or discussing their subgroup.^[ref]

Modulo seven, squaring the six nonzero congruence classes givesThus the set of quadratic residues is $Q_7=\{1,2,4\}$, and the quadratic nonresidues are $\{3,5,6\}$. In particular, $x^2\equiv 2(\mathrm{mod}7)$ has exactly the two solutions $x\equiv 3,4(\mathrm{mod}7)$: $3^2=9\equiv 2$ and $4^2=16\equiv 2$. Modulo eleven the quadratic residues are instead $Q_{11}=\{1,3,4,5,9\}$. Two is therefore a quadratic residue modulo seven and a quadratic nonresidue modulo eleven: being a quadratic residue depends on the modulus.

Why do the square roots come in pairs? If $x^2\equiv y^2(\mathrm{mod}p)$, the prime number $p$ divides $(x-y)(x+y)$, so it divides one factor: $y\equiv x$ or $y\equiv -x(\mathrm{mod}p)$. For nonzero $x$ these are distinct, because $p$ is an odd prime. Every nonempty nonzero fiber of a function of $s(x)=x^2$ therefore contains exactly two inputs. Pairing the $p-1$ nonzero congruence classes gives exactly $(p-1)/2$ quadratic residues and $(p-1)/2$ quadratic nonresidues. Including zero gives $(p+1)/2$ different squares, with one rather than two square roots for zero.

The quadratic residues form a subgroup of the multiplicative group of a finite field ${\mathbb{F}}_p^{\times }$, with index of a subgroup two. Indeed, one is a square, $(u^2)(v^2)=(uv{)}^2$, and $(u^2{)}^{-1}=(u^{-1}{)}^2$; the inverses exist because the inputs are nonzero in the prime field. Equivalently, the squaring group homomorphism has kernel of a group homomorphism $\{1,-1\}$ and image of a function $Q_p$. The apparent loss of a sign in squaring becomes a precise division of the nonzero arithmetic into two equal parts.

This structure turns a search for square roots into a yes-or-no test: Euler's criterion detects quadratic residues through modular exponentiation, and the Legendre symbol records the result as a sign. For a general integer modulus, the modular congruence $x^2\equiv a(\mathrm{mod}n)$ still makes sense, but the two-root count and the prime field argument need not survive. For example, $x^2\equiv 1(\mathrm{mod}15)$ has four solutions $1,4,11,14$; the Chinese remainder theorem separates the sign choices modulo three and five.

The congruence is soluble exactly for $p=2$ or $p\equiv 1(\mathrm{mod}4)$. For odd $p$, Fermat's little theorem applied to a prospective root forces $(p-1)/2$ even. Conversely, when $p\equiv 1(\mathrm{mod}4)$, pair opposite factors in $(p-1)!$ and use the Wilson theorem to obtain $(((p-1)/2)!{)}^2\equiv -1(\mathrm{mod}p)$.

A nonzero congruence class modulo an odd prime is a quadratic nonresidue when it is not a square. In the convention of quadratic residue, zero belongs to neither class. Thus $3,5,6$ are the quadratic nonresidues modulo seven, while $2,6,7,8,10$ are the quadratic nonresidues modulo eleven. No integer $x$ satisfies $x^2\equiv 3(\mathrm{mod}7)$, as the complete square map under quadratic residue shows.

A quadratic nonresidue is not an arithmetic dead end: multiplying by any fixed quadratic nonresidue $n$ exchanges the quadratic residues and the quadratic nonresidues. If $nq$ were a square for a square $q$, division by $q$ would make $n$ a square. Hence $n{Q}_p$ consists entirely of quadratic nonresidues; it has $(p-1)/2$ elements, because multiplication by nonzero $n$ is a bijection. It therefore equals the entire other coset of the quadratic residue subgroup. Modulo seven, $3\{1,2,4\}=\{3,6,5\}$.

The product of two quadratic nonresidues is consequently a quadratic residue: write them as $n{q}_1,n{q}_2$ in that same coset, and their product is $n^2{q}_1{q}_2$, a square. For example, $3\cdot 5\equiv 1(\mathrm{mod}7)$, whereas $2\cdot 3\equiv 6(\mathrm{mod}7)$ remains a quadratic nonresidue. The multiplicativity of the Legendre symbol packages these rules as ordinary sign multiplication.

For an odd prime $p$, the least quadratic nonresidue $n(p)$ is the smallest positive integer whose nonzero residue class is a quadratic nonresidue modulo $p$.

On a dyadic interval $Q<p\le 2Q$, every such exceptional prime makes all $Q^{0.01}$-smooth integers quadratic residues. By positive density of power-smooth integers, there are $\gg Q^2$ of these integers up to $Q^2$. Apply the variance form of the large sieve or its forbidden-residue consequence with interval length $Q^2$ and prime cutoff $2Q$. Each exceptional prime excludes $(p-1)/2$ residue classes and contributes at least a fixed positive amount to the sieve denominator. Hence each dyadic interval contains $O(1)$ exceptional primes. Summing the intervals gives the logarithmic bound.

// Target: analytic-number-theory.bigb

If, for every $\eta >0$, the smooth numbers up to $T$ with all prime factors at most $T^{\eta }$ have density at least $\kappa (\eta )>0$, then for fixed $\epsilon >0$ there are only $O_{\epsilon }(1)$ primes $p\le N$ with $n(p)>N^{\epsilon }$. Apply the variance form of the large sieve to the indicator function of the $N^{\epsilon }$-smooth numbers up to $N^2$. For every exceptional prime, all these numbers are nonzero quadratic residues, so half its nonzero residue classes are empty. Their variance contribution is at least one third of the square of the total count. The large sieve bounds the sum of contributions by a constant times $N^2$ times that count. The density assumption with $\eta =\epsilon /2$ finishes the argument.

For $\omega =e^{2\pi i/p}$ and the Legendre symbol $\chi$, the quadratic Gauss sum isIt equals $\sqrt{p}$ for $p\equiv 1(\mathrm{mod}4)$ and $i\sqrt{p}$ for $p\equiv 3(\mathrm{mod}4)$ with the standard choice of square root.

If $Q$ and $N$ are the nonzero square and nonsquare classes modulo eleven and $\omega =e^{2\pi i/11}$, thenTheir sum is $-1$, and their difference is the Quadratic Gauss sum $i\sqrt{11}$.

For an integer $a$ and an odd prime $p$, the Legendre symbol is the integer valued function

Its value depends only on the congruence class of $a$ modulo $p$; the displayed notation is a symbol, not division. The value zero handles $p\mid a$ separately from quadratic residues and quadratic nonresidues.^[ref]

For example, $(2/7)=1$, $(3/7)=-1$, $(14/7)=0$, and $(2/11)=-1$. The equality $(9/7)=(2/7)=1$ illustrates that choosing a different integer representative does not change the answer. An arbitrary odd composite denominator uses the Jacobi symbol, not the Legendre symbol. For instance,but two is not a square modulo fifteen: any such square root would also give a square root modulo three, where the only nonzero square is one. A Jacobi symbol of one therefore cannot replace the Legendre symbol's square test.

The Legendre symbol also counts square roots compactly. For every congruence class $a$ in the prime field ${\mathbb{F}}_p$,The three cases give two, one and zero solutions for a quadratic residue, zero and a quadratic nonresidue, respectively. This is useful when counting solutions of modular congruences involving polynomials: a solvability question becomes a sum of Legendre symbols, as in the complete Legendre-symbol sum and quadratic Legendre-symbol correlation.

For an odd prime $p$ and any integers $a,b$, the Legendre symbol obeysIn particular, if $p\nmid a$, then $(a^{-1}/p)=(a/p)$, where $a^{-1}$ is a modular multiplicative inverse. Multiplication by a nonzero square also leaves the Legendre symbol unchanged: $(a{r}^2/p)=(a/p)$ for $p\nmid r$.^[ref]

The subgroup and coset arguments under quadratic residue and quadratic nonresidue prove the sign rule without computing a large power: square times square is square, square times nonsquare is nonsquare, and nonsquare times nonsquare is square. If either factor is zero modulo $p$, both sides of the identity vanish. On ${\mathbb{F}}_p^{\times }$, the Legendre symbol is thus a group homomorphism to $\{1,-1\}$ whose kernel of a group homomorphism is the quadratic residue subgroup. Viewed on all integers, it is a completely multiplicative function and a Dirichlet character modulo $p$.

For an original calculation, factor the numerator $30=2\cdot 3\cdot 5$. Modulo seven, $(30/7)=(2/7)(3/7)(5/7)=1\cdot (-1)\cdot (-1)=1$, agreeing with $30\equiv 2(\mathrm{mod}7)$. Modulo eleven, the signs are instead $-1,1,1$, giving $(30/11)=-1$, agreeing with $30\equiv 8(\mathrm{mod}11)$. The same factorization can therefore certify different square behavior at different prime numbers.

Alternatively, Euler's criterion gives $(ab{)}^{(p-1)/2}\equiv a^{(p-1)/2}{b}^{(p-1)/2}$ modulo $p$. For nonzero factors both sides correspond to signs in $\{1,-1\}$. Since $p$ is odd, these signs are distinct modulo $p$, so the modular congruence proves the asserted equality of integers, not merely an equality of representatives.

For every odd prime $p$,Multiplication by a quadratic nonresidue permutes ${\mathbb{F}}_p$ and negates every term.

For every odd prime $p$,Equivalently, count the $p-1$ solutions of $t^2=y^2-1$ by factoring $(y-t)(y+t)=1$.

The number of $z\in \{1,\dots ,p-2\}$ for which both $z$ and $z+1$ are quadratic residues modulo $p$ is

For an odd prime $p$ and $p\nmid a$, Euler's criterion identifies the Legendre symbol by modular exponentiation:

Thus a quadratic residue gives one and a quadratic nonresidue gives minus one, represented by $p-1$ if a nonnegative remainder is used. The formula also holds when $p\mid a$, because $(p-1)/2>0$ and both sides are zero modulo $p$.^[ref]

For example, modulo seven the exponent is three: $2^3\equiv 1$ confirms that two is a quadratic residue, while $3^3\equiv 6\equiv -1$ confirms that three is a quadratic nonresidue. Modulo eleven the exponent is five, and $2^5=32\equiv 10\equiv -1$ confirms that two is a quadratic nonresidue. The test answers whether a square root exists; it does not itself return the roots $3,4$ of $x^2\equiv 2(\mathrm{mod}7)$.

A short proof needs only Fermat's little theorem and the root bound for a polynomial. Put $m=(p-1)/2$. If $a=x^2\ne 0$ in the prime field, then $a^m=x^{p-1}=1$. There are already $m$ such quadratic residues. The nonzero polynomial $T^m-1$ has polynomial degree $m$, so it has no other polynomial roots. Finally, for every nonzero $a$, Fermat's little theorem gives $(a^m{)}^2=a^{p-1}=1$. Factoring $(a^m-1)(a^m+1)=0$ in the field shows $a^m\in \{1,-1\}$; every quadratic nonresidue must take the remaining value $-1$. This proves the criterion without first finding a primitive root.

For a larger original example, decide whether seven is a quadratic residue modulo the prime number $101$. Exponentiation by squaring computes the required power without listing fifty squares:Therefore $(7/101)=-1$ and $x^2\equiv 7(\mathrm{mod}101)$ has no solution. Each intermediate product is reduced modulo $101$, as in modular exponentiation. The advantage is that exponentiation by squaring uses a number of multiplications proportional to the binary digit length of the exponent rather than testing every potential square root.

The odd prime hypothesis is essential. For the composite modulus nine, $2^{(9-1)/2}=2^4\equiv 7(\mathrm{mod}9)$, which is neither one nor minus one. Although four is a nonzero square modulo nine, $4^4\equiv 4(\mathrm{mod}9)$, so even the square-to-one implication fails. The Jacobi symbol and Euler pseudoprime discuss different questions for odd composite moduli; they do not make this a universal square test.

Every odd prime factor of an odd square plus four is one modulo four. The integer is five modulo eight, so at least one prime factor is five modulo eight. Choosing the odd square divisible by any proposed finite list excludes the list and proves infinitude.

For an odd prime $p$ and $p\nmid a$, let $m$ be the number of least positive residues amongthat exceed $p/2$. Then

For an odd prime $p$,For $p\nmid a$, write $a=g^m$ using a primitive root $g$; then the left side is $(-1{)}^m$, which is one exactly when $m$ is even and $a$ is a square.

Euler's criterion at $a=-1$ gives

For every odd prime,

If $q_1,\dots ,q_r$ listed all primes congruent to seven modulo eight, then for $n=8q_1\cdots q_r$ the odd number $(n^2-2)/2$ is seven modulo eight. Every prime factor is one or seven modulo eight, at least one is seven, and none is among the $q_i$, a contradiction.

Let ${\pi }_k(x)$ count primes at most $x$ congruent to $k$ modulo eight. Bounding the prime-power divisibility ofabove and its size below gives, for all sufficiently large $x$,

For an integer matrix $A$ and prime $p$, the commuting-matrix binomial theorem and divisibility of $\left(\genfrac{}{}{0ex}{}{p}{j}\right)$ for $0<j<p$ give

For $T={\sum }_{a=1}^{p-1}a(\frac{a}{p})$, one has $T=0$ when $p\equiv 1(\mathrm{mod}4)$, and $T\equiv 0(\mathrm{mod}p)$ for every $p>3$.

If $p\equiv 7(\mathrm{mod}8)$, the sum of the least positive quadratic residues below $p/2$ isThe proof uses $(\frac{2}{p})=1$ to compare the sum of all residues with its image under doubling.

For $p\nmid a$, the congruence $a{X}^2+bX+c=0(\mathrm{mod}p)$ has a solution exactly when its discriminant $b^2-4ac$ is zero or a quadratic residue modulo $p$.