Gauss's lemma (number theory)

Let $p$ be an odd prime and $a$ an integer with $p\nmid a$. Reduceto their least positive residue classes modulo $p$. If exactly $N$ of these representatives exceed $p/2$, Gauss's lemma statesThe symbol on the left is the Legendre symbol. For example, $p=7$ and $a=3$ give representatives $3,6,2$. Exactly one exceeds $7/2$, so $3$ is a quadratic nonresidue modulo $7$.

For a proof, replace every representative above $p/2$ by its negative modulo $p$, obtaining numbers $s_1,\dots ,s_m$ in $\{1,\dots ,m\}$. These numbers are distinct: equality would give $ai\equiv \pm aj(\mathrm{mod}p)$, forcing $i=j$ because $1\le i,j\le m$. They therefore form a permutation of $1,\dots ,m$. Multiplying the signed representatives givesThe factorial is invertible modulo $p$. Cancelling it and applying the Euler criterion proves the lemma. Counting signs can thus replace a potentially large modular exponentiation.