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 , and some number that is coprime to . We’d like to know whether is a quadratic residue modulo . Putting that another way, we’d like to find the value of the Legendre symbol . Helpfully, Euler‘s criterion tells us that . 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 . But it’s not quite so easy to calculate — we’d need to know modulo .
So let’s think about how we might work out modulo (obviously in a way that leads to an answer that isn’t just the Legendre symbol again!). We had a strategy for working out 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 , , …, 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 , , …, modulo in some order. So presumably here we should we should just multiply together , , …, . 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 should be , and it is not currently clear how we might get a minus sign.
Thinking about the minus sign, we could switch our focus from to . I’m going to introduce some (non-standard) notation here, which will hopefully help with writing this. For our fixed odd prime , write for the unique number congruent to modulo that lies in the set .
Let’s try some examples (both to get used to this notation and also to think about these multiples of ).
Say our fixed prime is , and we choose . Then
Or we might choose and . Then
Could it be that , , …, are , , …, 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 , , …, are congruent modulo .
Could two of them differ by just a sign? No, since no two of , , …, sum to 0 modulo .
Right. So it really is the case that , , …, are , , …, in some order, where each of those has a definite sign. Let’s say that 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 .
But is coprime to , so we can cancel it from both sides to obtain . And now Euler’s criterion gives . Since and both come from , we must have . And that’s Gauss‘s lemma proved! Perhaps I should state it clearly now.
Theorem (Gauss’s lemma): Let be an odd prime, and let be coprime to . Then , where .
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 , 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.