Gauss's lemma (number theory) (source code)

= Gauss's lemma
{disambiguate=number theory}
{c}
{wiki}

= Gauss lemma
{disambiguate=number theory}
{c}
{synonym}

Let $p$ be an <odd prime> and $a$ an <integer> with $p\nmid a$. Reduce
$$
a,2a,\ldots,ma,\qquad m=(p-1)/2,
$$
to their least positive <residue classes> modulo $p$. If exactly $N$ of these representatives exceed $p/2$, <Gauss's lemma (number theory)> states
$$
\left(\frac ap\right)=(-1)^N.
$$
The 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,\ldots,s_m$ in $\{1,\ldots,m\}$. These numbers are distinct: equality would give $ai\equiv\pm aj\pmod p$, forcing $i=j$ because $1\le i,j\le m$. They therefore form a <permutation> of $1,\ldots,m$. Multiplying the signed representatives gives
$$
a^m m!\equiv(-1)^N s_1\cdots s_m=(-1)^N m!\pmod p.
$$
The 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.