## Theorem 41: Gauss’s lemma

This result has a very uninformative name, I’m afraid, and it doesn’t identify the result uniquely, but it is the standard name so I’d better stick with it.

I’m going to write this post on the assumption that you know about Fermat’s little theorem and Euler’s criterion.  Fortunately, those links take you to places on this blog where you can read everything you need to know, and then you can come back here.

Ready?  Are you sitting comfortably?  Then we’ll begin.

Let’s fix an odd prime $p$, and some number $a$ that is coprime to $p$.  We’d like to know whether $a$ is a quadratic residue modulo $p$.  Putting that another way, we’d like to find the value of the Legendre symbol $\genfrac{(}{)}{}{}{a}{p}$.  Helpfully, Euler‘s criterion tells us that $\genfrac{(}{)}{}{}{a}{p} \equiv a^{\frac{p-1}{2}} \pmod{p}$.  I say “helpfully”, but it rather depends what we’re doing.  Euler’s criterion is great for some things.  For example, it makes it easy to compute $\genfrac{(}{)}{}{}{-1}{p}$.  But it’s not quite so easy to calculate $\genfrac{(}{)}{}{}{2}{p}$ — we’d need to know $2^{\frac{p-1}{2}}$ modulo $p$.

So let’s think about how we might work out $a^{\frac{p-1}{2}}$ modulo $p$ (obviously in a way that leads to an answer that isn’t just the Legendre symbol again!).  We had a strategy for working out $a^{p-1}$ in one proof of Fermat‘s little theorem (Proof 1 here).  Could we adapt that somehow, or use a similar idea?  I encourage you to try it before reading on.

That strategy was to multiply the numbers $a$, $2a$, …, $(p-1)a$ and to compute the answer in two different ways (that nonetheless give the same answer) using the fact that the numbers must be congruent to $1$, $2$, …, $p-1$ modulo $p$ in some order.  So presumably here we should we should just multiply together $a$, $2a$, …, $(\frac{p-1}{2})a$.  I can think of a few problems with that without even trying it.  One is that in the argument for Fermat’s little theorem, we knew that our list was equivalent to another list, so that we could multiply the numbers in two ways, whereas here we don’t seem to have another list.  Another problem is that we know that $a^{\frac{p-1}{2}}$ should be $\pm 1$, and it is not currently clear how we might get a minus sign.

Thinking about the minus sign, we could switch our focus from $\{0, 1, ..., p-1 \}$ to $\{-\frac{p-1}{2}, -\frac{p-1}{2}+1, ..., -1, 0, 1, 2, ..., \frac{p-1}{2}\}$.  I’m going to introduce some (non-standard) notation here, which will hopefully help with writing this.  For our fixed odd prime $p$, write $\langle b \rangle$ for the unique number congruent to $b$ modulo $p$ that lies in the set $\{-\frac{p-1}{2}, -\frac{p-1}{2}+1, ..., -1, 0, 1, 2, ..., \frac{p-1}{2}\}$.

Let’s try some examples (both to get used to this notation and also to think about these multiples of $a$).

Say our fixed prime is $p = 7$, and we choose $a = 2$.  Then $\displaystyle \begin{array}{rcl} \langle a \rangle & = & 2 \\ \langle 2a \rangle & = & -3 \\ \langle 3a \rangle & = & -1.\end{array}$

Or we might choose $p = 11$ and $a = 4$.  Then $\displaystyle \begin{array}{rcl} \langle a \rangle & = & 4 \\ \langle 2a \rangle & = & -3 \\ \langle 3a \rangle & = & 1 \\ \langle 4a \rangle & = & 5 \\ \langle 5a \rangle & = & -2. \end{array}$

Interesting!

Could it be that $\langle a \rangle$, $\langle 2a \rangle$, …, $\langle (\frac{p-1}{2})a \rangle$ are $\pm 1$, $\pm 2$, …, $\pm \frac{p-1}{2}$ in some order, where each of those occurs just once (with either $+$ or $-$ but not both)?

Well, could two of them be the same?  No, since no two of $a$, $2a$, …, $(\frac{p-1}{2})a$ are congruent modulo $p$.

Could two of them differ by just a sign?  No, since no two of $a$, $2a$, …, $(\frac{p-1}{2})a$ sum to 0 modulo $p$.

Right.  So it really is the case that $\langle a \rangle$, $\langle 2a \rangle$, …, $\langle (\frac{p-1}{2})a \rangle$ are $\pm 1$, $\pm 2$, …, $\pm \frac{p-1}{2}$ in some order, where each of those has a definite sign.  Let’s say that $\nu$ of them are negative.

Now, just as in our proof of Fermat’s little theorem, we multiply together the numbers in each list.  This time, we get $(\frac{p-1}{2})! a^{\frac{p-1}{2}} \equiv \langle a \rangle \langle 2a \rangle \dotsm \langle (\frac{p-1}{2})a \rangle \equiv (-1)^{\nu} (\frac{p-1}{2})! \pmod{p}$.

But $(\frac{p-1}{2})!$ is coprime to $p$, so we can cancel it from both sides to obtain $a^{\frac{p-1}{2}} \equiv (-1)^{\nu} \pmod{p}$.  And now Euler’s criterion gives $\genfrac{(}{)}{}{}{a}{p} \equiv (-1)^{\nu} \pmod{p}$.  Since $\genfrac{(}{)}{}{}{a}{p}$ and $(-1)^{\nu}$ both come from $\{-1,1\}$, we must have $\genfrac{(}{)}{}{}{a}{p} = (-1)^{\nu}$.  And that’s Gauss‘s lemma proved!  Perhaps I should state it clearly now.

Theorem (Gauss’s lemma): Let $p$ be an odd prime, and let $a$ be coprime to $p$.  Then $\genfrac{(}{)}{}{}{a}{p} = (-1)^{\nu}$, where $\nu = \# \{ k \in \{1, 2, \dotsc, \frac{p-1}{2}\}: \langle ka \rangle < 0 \}$.

And I seem to have given a proof on the way to finding the statement.  Which is handy.

Gauss’s lemma is not terribly useful for directly computing Legendre symbols for particular numbers: there are better tools.  But it is useful for some things.  I mentioned at the beginning that it would be nice to know the value of $\genfrac{(}{)}{}{}{2}{p}$, and it turns out that Gauss’s lemma makes this possible.  I’ll leave that as an exercise, I think.

Why is Gauss’s lemma called Gauss’s lemma?  Well, Gauss proved it on the way to proving the law of quadratic reciprocity (something that he did surprisingly often).  And the law of quadratic reciprocity really is a good way of computing Legendre symbols.

So, like all good lemmas, Gauss’s lemma perhaps isn’t massively exciting in its own right, but it’s extremely useful for proving exciting results.

### 3 Responses to “Theorem 41: Gauss’s lemma”

1. Number Theory: Lecture 7 « Theorem of the week Says:

[…] 23 (Gauss‘s Lemma): Let be an odd prime and let be an integer coprime to .  Then , where .  So to find , compute […]

2. Luis R. Guzman, Jr. Says:

Reblogged this on Guzman's Mathematics Weblog.

3. Number Theory: Lecture 7 | Theorem of the week Says:

[…] Proposition 23 (Gauss‘s Lemma): Let be an odd prime, and let be coprime to .  Then , where .  We proved this by showing that , , …, correspond to , , …, in some order, where each of these has a definite sign, and then multiplying them all together to show that .  Then we finished off using Euler’s criterion. […]