Gauss's Lemma

We are now going to learn about a very powerful lemma allowing us to prove quite a few theorems:

Lemma (Gauss): Suppose that p is an odd prime where $p \nmid a$ and among the set of least residues (mod p) of: $a, 2a, 3a, ..., \left ( \frac{p - 1}{2} \right )a$ there are exactly g that are greater than $\left ( \frac{p - 1}{2} \right )$, then $x^2 \equiv a \pmod p$ has a solution if g is even and no solution if g is odd. Hence $(a/p) \equiv (-1)^g$.

• Proof: Let $s_1, s_2, ..., s_g$ denote the least residues of the integer list $a, 2a, 3a, ..., \left ( \frac{p - 1}{2} \right )a$ (mod p) that are strictly greater than $\left ( \frac{p - 1}{2} \right )$ and let $r_1, r_2, ..., r_k$ denote the least residues of the integer list $a, 2a, 3a, ..., \left ( \frac{p - 1}{2} \right )a$ (mod p) that are less than or equal to $\left ( \frac{p - 1}{2} \right )$. Hence it follows that $g + k = \left ( \frac{p - 1}{2} \right )$.

• We know that no two elements s_i and s_k are congruent (mod p), since (a, p) = 1, then $g_ia \equiv g_ja \pmod p$ where 0 ≤ g_i ≤ $\left ( \frac{p - 1}{2} \right )$ and 0 ≤ g_j ≤ $\left ( \frac{p - 1}{2} \right )$ implies that $g_i = g_j$. Additionally, no two elements r_i and r_j are the same since (a, p) = 1, then $r_ia \equiv r_ja \pmod p$ where 0 ≤ r_i ≤ $\left ( \frac{p - 1}{2} \right )$ and 0 ≤ r_j ≤ $\left ( \frac{p - 1}{2} \right )$ implies that $r_i = r_j$.

• Consider the set of integers $r_1, r_2, ..., r_k, p - s_1, p - s_2, ... , p - s_g$. Each of these integer n in this set satisfy the condition 1 ≤ n ≤ $\left ( \frac{p - 1}{2} \right )$ and there are exactly $\left ( \frac{p - 1}{2} \right )$ elements in this set. All we need to do it prove that all integers in this set are different by showing that $r_i \not\equiv p - s_j \pmod p$ for any i, j.

• Suppose that $r_i \equiv p - s_j \pmod p$. With some manipulation it follows that $r_i + s_j \equiv p \pmod p$ or more appropriately that $r_i + s_j \equiv 0 \pmod p$. For some integers t and u, we know that $r_i \equiv ta \pmod p$ and that $s_j \equiv ua \pmod p$. Hence it follows that $ta + ua \equiv 0 \pmod p$, or rather $a( t + u ) \equiv 0 \pmod p$. Since $(a, p) = 1$, we can cancel the a to get that $u + t \equiv 0 \pmod p$, but this is impossible since we know that 1 ≤ t ≤ $\left ( \frac{p - 1}{2} \right )$ and 1 ≤ u ≤ $\left ( \frac{p - 1}{2} \right )$, so then 2 ≤ t + u ≤ $p - 1$. Hence, all of the elements $r_1, r_2, ..., r_k, p - s_1, p - s_2, ... , p - s_g$ are distinct and are a rearrangement of $1, 2, 3, ..., \left ( \frac{p - 1}{2} \right )$.

• It thus follows that $r_1r_2...r_k(p-s_1)(p-s_2)...(p-s_g) = 1 \cdot 2 \cdot ... \cdot \left ( \frac{p - 1}{2} \right )$. We know that $p - s_i \pmod p$ becomes (-1)s_i for any i, hence we get that: $r_1r_2...r_k s_1 s_2 ... s_g (-1)^g = \left ( \frac{p - 1}{2} \right )!$. We started earlier that $r_1, r_2, ... r_k$ and $s_1, s_2, ..., s_g$ were the least residues of the list $a, 2a, 3a, ..., \left ( \frac{p - 1}{2} \right )a$ (mod p), hence it follows that: $a^{\left ( \frac{p - 1}{2} \right )} (-1)^g \left ( \frac{p - 1}{2} \right )! \equiv \left ( \frac{p - 1}{2} \right ) ! \pmod p$. Since $(\left ( \frac{p - 1}{2} \right )! , p ) = 1$, we can cancel to obtain that:

(1)

\begin{align} a^{\left ( \frac{p - 1}{2} \right )} (-1)^g \equiv 1 \pmod p \\ a^{\left ( \frac{p - 1}{2} \right )} \equiv (-1)^g \pmod p \\ \end{align}

• By Euler's Criterion we know that $a^{\left ( \frac{p - 1}{2} \right )} \equiv (a/p) \pmod p$, hence it follows that $(a/p) = (-1)^g$.

Example

Using Gauss's Lemma, determine if the linear congruence $x^2 \equiv 6 \pmod {11}$ has solutions or no solutions.

From Gauss's Lemma, we are going to look at the set of $\left ( \frac{p - 1}{2} \right ) = \left ( \frac{11 - 1}{2} \right ) = 5$ integers: $(1 \cdot 6), (2 \cdot 6), (3 \cdot 6), (4 \cdot 6), (5 \cdot 6)$. In least residue (mod 11) we obtain the set of integers:

(2)

\begin{equation} 6, 1, 7, 2, 8 \end{equation}

Now we will count how many of these integers are greater than $\left ( \frac{11 - 1}{2} \right ) = 5$. There are precisely 3 that are greater. Hence by Gauss's Lemma, since g = 3 and g is odd, then $x^2 \equiv 7 \pmod {11}$ has no solutions.