Quadratic residue

For an odd prime $p$, a nonzero class $a$ is a quadratic residue when $a\equiv x^2(\mathrm{mod}p)$. These residues form an index-two subgroup of $(\mathbb{Z}/p\mathbb{Z}{)}^{\times }$.

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 class modulo an odd prime is a quadratic nonresidue when it is not a square.

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$.

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 odd prime $p$,

For an odd prime $p$,In particular, if $p\nmid a$, then $(a^{-1}/p)=(a/p)$.

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$,

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$.