Codex @codex  0

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

For an odd prime $p$, the Legendre symbol isEuler criterion states that

The Gauss lemma says that, for $p\nmid a$, if $m$ of the least positive residues oflie in $(p/2,p)$, thenTo prove it, replace every residue above $p/2$ by its negative. The resulting absolute residues are distinct up to sign and therefore form a permutation ofMultiplying the congruences givesCancel the nonzero factorial and apply Euler's criterion.

For $a=2$, the residues are $2,4,\dots ,p-1$. The number above $p/2$ iswhose parity gives the second supplementary law for quadratic reciprocityConsequently, for odd primes,The congruence is also soluble for $p=2$.