Skip to main content

Section 9.2 Gauss' Lemma

Since \(\gcd(a, p) = 1,\) all of the \((p-1)/2\) integers of \(S\) are incongruent modulo \(p\) and none are zero. Let \(r_1,..., r_m\) be those remainders upon division by \(p\) that are between \(0\) and \(p/2 \hspace{2mm} (0\lt r_i \lt p/2)\) and \(s_1,..., s_n\) be those remainders upon division by \(p\) that are between \(p/2\) and \(p \hspace{2mm} (p/2 \lt s_i \lt p).\) Then \(m + n = (p-1)/2\) and the integers

\begin{equation*} r_1,..., r_m, p-s_1,..., p-s_n \end{equation*}

are all positive and less that \(p/2.\)

To show these integers are all distinct, we only need to show that \(p-s_i\) is not equal to any \(r_j.\) So assume to the contrary that

\begin{equation*} p-s_i = r_j \end{equation*}

for some \(i\) and \(j.\) Then there exists \(u, v \hspace{2mm} (1 \leq u, v\leq (p-1)/2)\) such that \(s_i \equiv ua\pmod{p}\) and \(r_j \equiv va\pmod{p}.\) So

\begin{equation*} (u + v)a \equiv s_i + r_j = p \equiv 0\pmod{p} \hspace{2mm}\Rightarrow \hspace{2mm} u + v \equiv 0\pmod{p}, \end{equation*}

which is impossible since \(1\leq u, v \leq (p- 1)/2.\)

So

\begin{equation*} \{r_1,..., r_m, p-s_1,..., p-s_n\} = \{1, 2,..., (p-1)/2\}, \end{equation*}

and so the product of them is \(\left(\dfrac{p-1}{2}\right)!.\) Now since the product of the remainders is also congruent modulo \(p\) to the product of the elements of \(S,\) we have

\begin{align*} \left(\frac{p-1}{2}\right)! \amp = r_1\cdots r_m(p-s_1)\cdots (p-s_n)\\ \amp = r_1\cdots r_m(-s_1)\cdots (-s_n)\pmod{p}\\ \amp = (-1)^n r_1\cdots r_m(s_1)\cdots (s_n)\pmod{p}\\ \amp = (-1)^n a\cdot 2a\cdots \left(\frac{p-1}{2}\right)a\pmod{p}\\ \amp = (-1)^n a^{(p-1)/2}\left(\frac{p-1}{2}\right)! \pmod{p} \end{align*}

so that since \(\gcd\left(\left[\dfrac{(p-1)}{2}\right]!, p\right) = 1\) we have

\begin{equation*} 1 \equiv (-1)^n a^{(p-1)/2}\pmod{p}. \end{equation*}

Some rearrangement and Euler's Criterion gives

\begin{equation*} (a/p) \equiv a^{(p-1)/2} \equiv (-1)^n \pmod{p} \end{equation*}

so that we have

\begin{equation*} (a/p) = (-1)^n. \end{equation*}