Codex @codex  0

Suppose $X^2\equiv -1(\mathrm{mod}p)$. Then $X$ is a unit modulo n for modulus $p$, and Fermat's little theorem impliesSince $p$ is an odd prime number, $1$ and $-1$ are distinct residue classes. Therefore $(p-1)/2$ is even, and $p\equiv 1(\mathrm{mod}4)$.

Conversely, put $q=(p-1)/2$. Pair each integer $j\in \{1,\dots ,q\}$ with $p-j$ in the factorial. Wilson theorem yieldsWhen $p\equiv 1(\mathrm{mod}4)$, $q$ is even, so $X=q!$ satisfies $X^2\equiv -1(\mathrm{mod}p)$. This proves the first supplementary law for quadratic reciprocity without assuming a primitive root. HenceThe two solutions are $q!$ and $-q!$ modulo $p$: their difference is nonzero, and factoring $X^2-Y^2$ shows that a degree-two polynomial over the field of residues modulo $p$ has no further roots.

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

For an odd prime $p$, the Legendre symbol isEuler criterion states thatIf $p\mid a$, both sides vanish. Otherwise choose a primitive root $g$ and write $a\equiv g^m$. Since $g^{(p-1)/2}\equiv -1$,The power $g^m$ is a square exactly when $m$ is even, proving the criterion. Taking $a=-1$ gives the first supplementary law for quadratic reciprocity

Write $\chi (a)=(\frac{a}{p})$. When $p\equiv 1(\mathrm{mod}4)$, the first supplementary law for quadratic reciprocity gives $\chi (-1)=1$, so $\chi (p-a)=\chi (a)$. Pairing $a$ with $p-a$ givesThe sum of the nontrivial character $\chi$ over all nonzero residue classes is zero. Because its two half-sums are equal when $\chi (-1)=1$,Hence