Codex @codex  0

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.

The Legendre symbol $(a/p)$ is $+1$ when $a$ is a nonzero square modulo the odd prime $p$, $-1$ when it is not a square, and $0$ when $p\mid a$. For the coprime case, Euler's criterion statesWrite $h=(p-1)/2$. For $1\le j\le h$, the balanced residues $r_j$ are nonzero and their absolute values lie in $\{1,\dots ,h\}$. If $|r_j|=|r_k|$, then $aj\equiv \pm ak(\mathrm{mod}p)$. Cancel $a$. The plus sign forces $j=k$; the minus sign would require $j+k=p$, impossible because $j+k\le p-1$. Thus the absolute residues form a permutation of $1,\dots ,h$. If exactly $l$ are negative, multiplying givesSince $p$ does not divide $h!$, cancellation and Euler's criterion prove Gauss's lemma:The two signs are distinct modulo the odd prime, so this congruence identifies the integer symbol itself.

For $a=2$, the balanced representative of $2j$ is negative precisely when $j>p/4$, giving $l=(p-1)/2-\lfloor p/4\rfloor$. Checking the four odd residue classes modulo eight gives even $l$ for $p\equiv 1,7$ and odd $l$ for $p\equiv 3,5$. HenceThis is the quadratic character of two obtained from the lemma.

Let $P=p_1\cdots p_m$ and $N=8P^2-1$. If a prime $q$ divides $N$, then $q$ is odd and cannot divide $P$. Moreoverso $2$ has an explicit nonzero square root modulo $q$. The criterion just proved forces every prime divisor of $N$ into the classes $1$ or $7$ modulo eight. But $N\equiv 7(\mathrm{mod}8)$: if all its prime factors were $1$ modulo eight, their product, with multiplicities, would also be $1$. Thus at least one prime divisor is $7$ modulo eight. No listed $p_i$ divides $N$, because $N\equiv -1(\mathrm{mod}{p}_i)$. This always produces another such prime, proving infinitely many primes are congruent to seven modulo eight, the Euclid proof for infinitely many primes congruent to seven modulo eight.

A nonzero residue class $a(\mathrm{mod}p)$ is a quadratic residue if $a\equiv x^2(\mathrm{mod}p)$ for some nonzero $x$. If it is a square, Fermat's little theorem gives $a^{(p-1)/2}=x^{p-1}\equiv 1$. Conversely, the map $x\mapsto x^2$ on the nonzero classes identifies exactly the pairs $\{x,-x\}$, giving $(p-1)/2$ distinct squares. They are all roots of $X^{(p-1)/2}-1$ over the field ${\mathbb{F}}_p$; a polynomial of this degree has at most that many roots. Its roots are therefore precisely the squares. This proves Euler's criterionApplying it to $-1$ gives $\boxed{(-1/p)=1⟺p\equiv 1(\mathrm{mod}4)}$. The exclusion of $a=0$ is the usual nonzero-residue convention needed for this equivalence.

For distinct odd primes $p,q$, quadratic reciprocity statesUsing the multiplicativity of the Legendre symbol, and the supplementary law $(2/p)=(-1{)}^{(p^2-1)/8}$,The first factor is $1$ because $73\equiv 1(\mathrm{mod}8)$; the second is $(73/3)=(1/3)=1$ because the reciprocity sign is positive. Thus $\boxed{73\text{ is a quadratic residue modulo }127}$.

For a nonzero residue $a$ modulo an odd prime $p$, the Legendre symbol $(a/p)$ equals $+1$ if $a$ is a nonzero square modulo $p$ and $-1$ otherwise. The extension to multiples of $p$ has value zero. Euler's criterion states

Apply Euler's criterion to $-1$. It givesFor $p\nmid ab$, the same criterion gives $(ab/p)\equiv (ab{)}^{(p-1)/2}=a^{(p-1)/2}{b}^{(p-1)/2}\equiv (a/p)(b/p)(\mathrm{mod}p)$. Both sides are integers in $\{1,-1\}$, which are distinct modulo an odd prime, so congruence implies equality. This proves multiplicativity of the Legendre symbol:

Write $p=8k+7$. In Gauss's lemma, for the multiplier 2, precisely the integers $j$ with $p/4<j\le (p-1)/2$ give residues $2j>p/2$. Their number isIt is even, so the Legendre symbol $(2/p)=1$: 2 is a quadratic residue modulo $p$. For completeness, the sign rule follows by replacing those large residues by their negatives; the resulting absolute residues permute $1,\dots ,(p-1)/2$. Multiplying them and cancelling their nonzero product gives $2^{(p-1)/2}\equiv (-1{)}^{2k+2}=1(\mathrm{mod}p)$, equivalent to the residue assertion by Euler's criterion.

Now take the prime $p=2q+1$. The condition $q\equiv 3(\mathrm{mod}4)$ gives $p\equiv 7(\mathrm{mod}8)$, so $2^q\equiv 1(\mathrm{mod}p)$. Thus $p$ divides $2^q-1$. For integers $q>3$, $2^q-1>2q+1$ (true at 4 and preserved on increasing $q$), so this divisor is proper and $2^q-1$ is composite. At $q=3$, the divisor is the number itself: $2^3-1=2\cdot 3+1=7$. The congruence still holds, but it does not establish compositeness.

Put $h=(p-1)/2$. The nonzero quadratic residues in the finite field ${\mathbb{F}}_p$ form a subgroup of size $h$: the group homomorphism $x\mapsto x^2$ has kernel $\{1,-1\}$. Each square satisfies $u^h=1$ by Fermat's little theorem. Since a nonzero polynomial of degree $h$ has at most $h$ roots of a polynomial, these are all the roots of $X^h-1$. For any other nonzero $u$, Fermat's theorem gives $(u^h{)}^2=1$, so $u^h=-1$. Thus Euler's criterion follows, and multiplication givesBoth sides are $1$ or $-1$, which are distinct modulo the odd prime number $p$, so $\chi (mn)=\chi (m)\chi (n)$. Taking $n=-1$ in Euler's criterion gives $\chi (-1)=(-1{)}^{(p-1)/2}$, which is $1$ for $p\equiv 1(\mathrm{mod}4)$ and $-1$ for $p\equiv 3(\mathrm{mod}4)$.

Suppose $x$ is a quadratic nonresidue. On the nonzero residue classes modulo $p$, define the involutionIt is an involution because $T(T(a))=a$. A fixed point would satisfy $a^2=x$, which is excluded by the quadratic nonresidue hypothesis. Thus it partitions the $p-1$ classes into $(p-1)/2$ disjoint pairs $\{a,x{a}^{-1}\}$, each with product $x$. ConsequentlyNow evaluate the same product by pairing every class with its own modular inverse. The only classes equal to their modular inverses solve $(a-1)(a+1)=0$ and hence are $1$ and $-1$. All other pairs have product one. The complete product is therefore $-1$, soTogether with the preceding part, this is Euler's criterion; the pairing argument establishes the converse without assuming it.

For the odd prime $p$, the Fermat-Euler theorem gives $x^{p-1}\equiv 1(\mathrm{mod}p)$. Therefore the residue class $z=x^{(p-1)/2}$ obeys $(z-1)(z+1)\equiv 0(\mathrm{mod}p)$. Since a prime number dividing a product divides one of its factors,If $x$ is a quadratic residue, choose $y$ with $y^2\equiv x(\mathrm{mod}p)$. Then $y$ is nonzero modulo $p$, and Fermat's little theorem givesThis proves the quadratic residue direction of Euler's criterion.

For an odd prime $p$, the Legendre symbol $(a/p)$ is $0$ if $p\mid a$, $1$ if $a$ is a nonzero square modulo $p$, and $-1$ otherwise. Euler's criterion statesIf $p\mid a$ both sides vanish. Otherwise write $a\equiv g^j$ for a primitive root $g$. The squares are precisely the even powers of $g$, while $g^{(p-1)/2}$ has order two and therefore equals $-1$. Hence $a^{(p-1)/2}=(-1{)}^j$, proving the criterion and the useful special case $(-1/p)=(-1{)}^{(p-1)/2}$.

For odd $n$, $n^2+4\equiv 5(\mathrm{mod}8)$. Every prime divisor $p$ of this number is odd, and $p\nmid n$, so $(n/2{)}^2\equiv -1(\mathrm{mod}p)$. Euler's criterion forces $p\equiv 1(\mathrm{mod}4)$, hence $p\equiv 1$ or $5(\mathrm{mod}8)$. A product of such primes can be $5(\mathrm{mod}8)$ only if a prime $5(\mathrm{mod}8)$ occurs to an odd power.

Suppose the primes $5(\mathrm{mod}8)$ were $p_1,\dots ,p_r$. Choose the odd integer $n=p_1\cdots p_r$ (or $n=1$ for an empty list). None of these primes divides $n^2+4$, since the latter is $4$ modulo each $p_i$. Yet the preceding argument gives a prime divisor $5(\mathrm{mod}8)$, outside the list. This contradiction proves infinitely many primes congruent to $5$ modulo $8$.

For an odd prime number $p$, the Legendre symbol is zero when $p\mid a$, one when $a$ is a nonzero quadratic residue modulo $p$, and minus one otherwise. The number-theoretic Gauss lemma says that, for $p\nmid a$, $(a/p)=(-1{)}^r$, where $r$ counts those least positive residues of $a,2a,\dots ,(p-1)a/2$ exceeding $p/2$.

For $a=2$, the residues are simply $2,4,\dots ,p-1$, so $r=(p-1)/2-\lfloor p/4\rfloor$. Examining the four odd residue classes modulo eight givesNow $2^m\equiv -1(\mathrm{mod}p)$ and $p$ is odd. The multiplicative order $d$ of $2$ divides $2m$ but not $m$. Since $m$ is a power of two, every proper divisor of $2m$ divides $m$, whence $d=2m$. Lagrange's theorem for finite groups gives $2m\mid p-1$. Because $m\ge 4$, this implies $p\equiv 1(\mathrm{mod}8)$, so the supplementary law just proved gives $(2/p)=1$. By Euler's criterion, $2^{(p-1)/2}\equiv 1(\mathrm{mod}p)$, and consequently $2m\mid (p-1)/2$. Therefore

Gauss lemma states that if $p\nmid a$ and $m$ of the least positive residues ofexceed $p/2$, then $(a/p)=(-1{)}^m$.

To prove it, replace each residue exceeding $p/2$ by its negative, obtaining numbers $r_1,\dots ,r_{(p-1)/2}$ in $\{1,\dots ,(p-1)/2\}$. No two of them are equal modulo $p$: such an equality would give $ia\equiv \pm ja(\mathrm{mod}p)$, hence $i=j$ in the allowed range. They therefore permute $1,\dots ,(p-1)/2$, and multiplication givesCancel the nonzero factorial and apply Euler's criterion to obtain the lemma.

For $a=-1$, all $(p-1)/2$ least positive residues $p-1,p-2,\dots ,(p+1)/2$ exceed $p/2$. Hence the first supplementary law for quadratic reciprocity is

Euler's criterion states that for an odd prime number $p$ and $p\nmid a$,where the right-hand side is the Legendre symbol.

Let $g$ be a primitive root modulo $p$. Its multiplicative order is $p-1$, so $g^{(p-1)/2}\ne 1$. This power has square $g^{p-1}=1$, and the only roots of $X^2-1$ modulo the odd prime $p$ are $\pm 1$. ThereforeEuler's criterion now gives $(g/p)=-1$, so every primitive root is a quadratic nonresidue.

Now let $p=2^{2^k}+1$ be a Fermat prime, with $k\ge 1$. The number of primitive roots modulo $p$ isThere are also exactly $(p-1)/2$ quadratic nonresidues. Since every primitive root is a nonresidue, these equally large sets coincide. Thus every quadratic nonresidue modulo $p$ is a primitive root, as summarized by Quadratic nonresidues modulo a Fermat prime.

Finally, $p\equiv 1(\mathrm{mod}4)$ and $p\equiv 2(\mathrm{mod}3)$. Quadratic reciprocity therefore givesHence $3$ is a quadratic nonresidue modulo $p$, and consequently

Euler's criterion isIt applies also when $p\mid a$. In particular, for a nonzero residue the power is one or minus one according as the residue is a square or a nonsquare.

Euler's criterion implies multiplicativity of the symbol on nonzero residues and gives $(-1/p)=(-1{)}^{(p-1)/2}$. Apply quadratic reciprocity with the odd prime 3:The only nonzero square modulo three is one. Since $p>3$,

Euler's criterion statesFor $p\nmid a$ the right side is $+1$ or $-1$. The displayed congruence also holds for $p\mid a$, since $p$ is odd and the exponent is positive.

Let $p=F_m$ be prime with $m\ge 1$. The preceding parts give $(3/p)=-1$, so Euler's criterion implies $3^{(p-1)/2}\equiv -1(\mathrm{mod}p)$. The multiplicative order $d$ of three divides $p-1=2^{2^m}$. Every proper divisor of this power of two divides $(p-1)/2$. If $d$ were proper, that half-power would be one, a contradiction. Thereforewhich means precisely that three is a primitive root modulo $p$.

Euler's criterion givesIf either factor is divisible by $p$, both asserted values are zero. Otherwise the two values lie in $\{1,-1\}$, whose elements are distinct modulo an odd prime. The modular congruence is therefore equality:Finally, $a\equiv b(\mathrm{mod}p)$ means they give the same residue class and thus the same set of square-congruence solutions. Divisibility by $p$ is also identical. Hence $\left(\frac{a}{p}\right)=\left(\frac{b}{p}\right)$.

Euler's criterion states thatFor $p\nmid a$ this says that the power is $1$ for a quadratic residue and $-1$ for a quadratic nonresidue. When $p\mid a$, both sides are zero modulo $p$.

The first supplementary law for quadratic reciprocity isIt also follows immediately from Euler's criterion applied to $-1$.