Gauss's Lemma (Number Theory)

Lemma

Let $p$ be an odd prime.

Let $a \in \Z: a \not \equiv 0 \pmod p$.

Let $S = \left\{{a, 2a, 3a, \ldots, \dfrac {p-1} 2 a}\right\}$.

Let $n$ denote the number of elements of $S$ whose least positive residue modulo $p$ is greater than $\dfrac p 2$.

Then $\left({\dfrac a p}\right) = \left({-1}\right)^n$, where $\left({\dfrac a p}\right)$ is the Legendre symbol.

Proof

• First note that no two elements of $s$ are congruent modulo $p$:

Let $r a \equiv s a \pmod p$ for some $r, s$ such that $1 \le s \le r \le \dfrac {p-1} 2$.

As $a \perp p$, we have that $r a \equiv s a \implies r \equiv s \pmod p$ from Cancellability of Congruences.

Now $r \equiv s \pmod p$ can happen only when $r = s$ as $0 \le r - s \le \dfrac {p-1} 2$.

• Next, no element of $S$ is congruent modulo $p$ to $0$.

This is because $r a \equiv 0 \pmod p$ when $a \not \equiv 0$ requires $r \equiv 0$ which doesn't happen.

• Now, we create $S'$ from $S$ by replacing each element of $S$ by its least positive residue modulo $p$.

Arranging $S'$ into increasing order, we get:

$S' = \left\{{b_1, b_2, \ldots, b_m, c_1, c_2, \ldots, c_n}\right\}$

where $b_m < \dfrac p 2 < c_1$ and $m + n = \dfrac {p-1}2$.

As $p$ is an odd prime, $\dfrac p 2$ is not an integer so neither $b_m$ nor $c_1$ can be equal to $\dfrac p 2$.

• Now we let $S'' = \left\{{b_1, b_2, \ldots, b_m, p-c_1, p-c_2, \ldots, p-c_n}\right\}$

We need to show that $S'' = \left\{{1, 2, 3, \ldots, \dfrac {p-1} 2}\right\}$.

Now:

• all the elements of $S''$ are positive, as all the $c_j < p$
• the largest one is either $b_m$ or $p - c_1$
• there are $\dfrac {p-1} 2$ of them
• they are all less than $\dfrac p 2$.

So $S''$ contains $\dfrac {p-1} 2$ positive integers all less than $\dfrac p 2$.

So all we need to do is show that they are distinct.

As all the elements of $S'$ are distinct, the $m$ elements $b_1, b_2, \ldots, b_m$ are distinct.

Similarly, so are the $n$ elements $p-c_1, p-c_2, \ldots, p-c_n$.

So, we suppose $b_i = p - c_j$ for some $i, j$ and try to derive a contradiction.

So:

$p = b_i + c_j \equiv r a + s a \pmod p$

for some $r, s$ such that $1 \le r, s \le \dfrac {p-1} 2$.

But from:

$p \equiv \left({r+s}\right) a \pmod p$ and $a \not \equiv 0 \pmod p$

we apply Euclid's Lemma to get $r + s \equiv 0 \pmod p$.

But this is impossible since $2 \le r + s \le p-1$.

This establishes that $S'' = \left\{{1, 2, 3, \ldots, \dfrac {p-1} 2}\right\}$.

• Now, we multiply all the elements of $S''$ together:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \left({\frac {p-1} 2}\right)!\)	\(=\)	\(\displaystyle b_1 b_2 \cdots b_m \left({p-c_1}\right) \left({p-c_2}\right) \cdots \left({p-c_n}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\equiv\)	\(\displaystyle b_1 b_2 \cdots b_m \left({-c_1}\right) \left({-c_2}\right) \cdots \left({-c_n}\right)\)	\(\displaystyle \)	\(\displaystyle \pmod p\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\equiv\)	\(\displaystyle \left({-1}\right)^n b_1 b_2 \cdots b_m c_1 c_2 \cdots c_n\)	\(\displaystyle \)	\(\displaystyle \pmod p\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\equiv\)	\(\displaystyle \left({-1}\right)^n a \times 2a \times 3a \times \cdots \frac{p-1} 2 a\)	\(\displaystyle \)	\(\displaystyle \pmod p\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\equiv\)	\(\displaystyle \left({-1}\right)^n a^{\left({\frac {p-1} 2}\right)} \times \left({\frac {p-1} 2}\right)!\)	\(\displaystyle \)	\(\displaystyle \pmod p\)	\(\displaystyle \)	as the elements in $S'$ are congruent, in some order, to those in $S$

Now, from GCD with Prime, $\gcd \left\{{p, \left({\dfrac {p-1} 2}\right)!}\right\} = 1$.

So from Cancellability of Congruences the term $\left({\dfrac {p-1} 2}\right)!$ can be cancelled from both sides of the above congruence:

$1 \equiv \left({-1}\right)^n a^{\left({\frac {p-1} 2}\right)} \pmod p$

Finally, from the definition of the Legendre symbol, we have:

$\left({\dfrac a p}\right) \equiv a^{\left({\frac {p-1} 2}\right)} \pmod p$

Multiplying both sides of the congruence by $\left({-1}\right)^n$ gives us:

$\left({\dfrac a p}\right) = \left({-1}\right)^n$

$\blacksquare$

Source of Name

This entry was named for Carl Friedrich Gauss.