Alice: Fine, but I want to move first.
Bob: What? This is my game!
A: Precisely! I’m sure you have figured out the strategy to win by now, so let me at least enjoy the game for a little bit.
B: Alright, fine. Are you sure you’ve got all the rules?
A: It’s not like there are too many of them.
B: So we first agree on the number of moves and another number .
A: Sure enough. Then I choose a number and take its square…
B: …then I choose another number and add its square to yours…
A: …and we just keep adding squares, summing of them in total.
B: That’s right, and you want to prevent the total sum from being a multiple of .
A: It doesn’t sound like a very exciting game, I don’t really think I want to play it.
B: Really? Not even once?
A: I mean, that’s just adding numbers! And after all, shouldn’t we be sending encrypted messages to each other or something instead of playing games?
B: You know, cryptography can be a bit like a game as well… either way, I just wanted to do something else for one. What should I do with the game now? Just forget about it?
A: If you care about your game so much we can try to work something out with it without playing it.
B: I don’t know why you don’t want to play so much, but I like the idea. So, do you want to work out the winning strategy?
A: Hmm, that’s what everyone would do… how about the number of possible plays?
B: Well, we can choose arbitrary integers… but everything only matters modulo , so I guess we can count possibilities that way.
A: We clearly have possible choices for each , so there are possible plays. Now, how many of these are wins for me?
B: So basically we are counting solutions to
A: Congruences are always nicer with prime number modulus… can we assume that the number which we have conveniently happened to call is a prime?
B: Sure, let’s even say it’s an odd prime. But still, how could we approach this?
A: Let’s try induction. Everything can be proven by induction, right?
B: We’ll see… Base case seems easy, so let’s get to the induction step right away.
A: Say I have chosen some number . Number of solutions with this is the same as the number of solutions of
but this congruence has something else on the right hand side than zero…
B: True. I’m afraid we will have to deal with a more general problem if we want induction to work. So I think we should consider the number of solutions to the congruence
A: Let’s give it a name, say we will call it . But then even the case with one variable seems less trivial…
B: Yeah, there probably won’t be any simple expression which is on zero, on all other squares modulo and on nonsquares.
A: Wait, actually, if you were to subtract from each of these numbers, we get expression which is on zero, on squares and on nonsquares. This is precisely the Legendre symbol!
B: Ah! So we can say that .
A: This gave me an idea. To find we can consider all tuples satisfying , and then consider in how many ways these can be replaced with squares.
B: If I understand correctly, what you are saying can be expressed as
the being taken modulo , of course.
A: This gives us some expression for this number, but I suppose we both want something more “closed form”. This mess would be horrible to compute. Just imagine expanding this product!
B: Yeah, it would probably… actually, wait a moment. There will be a lot of cancellation in that sum. For example, consider the term in the expanded product. In the sum, we can choose independently and then we have unique choice of . So when summing, this term contributes
since there is the same number of quadratic residues as nonresidues modulo , so the first sum is zero.
A: That’s excellent! So we are only left with sums over and over product of all the Legendre symbols. The ones are easy to count, so we are left with
B: Multiplicativity of Legendre’s symbol is very useful; at the very least it reduces the number of brackets. Do you think there will be such a cancellation in the last sum as well?
A: I guess so; the term is probably dominating. We can try grouping the terms in which the are the same, just permuted. For example if we group the terms corresponding to a cyclic permutation of …
B: Wait, there might be less than of them if some of the are equal.
A: Oops, true. But the number of such terms will certainly divide . So if happened to be prime, then there would be either one such term, which means that all are equal, or exactly of them… if we were to look modulo , the latter terms would cancel out, so we can say
If are distinct odd primes, then has a unique solution modulo , so then
Isn’t that cool?
B: I suppose it is, but we want to find exact value of , so working modulo won’t help us, especially for when is not prime. Maybe we should try to go back to induction?
A: Alright. But I still think that it’s cool to consider the number of solutions of an equation modulo modulo .
B: For the number of solutions clearly only depends only on whether is zero, a quadratic residue or a nonresidue. I think the same should be true for larger : if we have two nonzero squares , then from a solution
of one equation to a solution
of another equation.
A: This gives a bijection! So we can say that numbers are the same for all nonzero squares! Also, a ratio of nonresidues is a residue, so we can do pretty much the same thing for nonsquares!
B: So it might be useful to somewhat forget about the number and just think about whether it is or not a square. So we can let be a placeholder for a squares, so that is a well-defined number…
A: …and we can also have for nonsquares!
B: Wait, why a triangle?
A: Because it’s not a square.
B: …fair enough.
A: Oh! We can also have…
B: We are not using in place of .
A: …fine. Anyways, let’s try to find out something about . First of all, might be zero.
B: In this case, . We know how many solutions this has – it’s .
A: Good, now let’s see what happens if is nonzero. For equality to hold, must be . Is this a quadratic residue or a nonresidue?
B: It depends on whether is a square or not. Thankfully we have the Euler’s criterion, which tells us that it’s a square precisely when .
A: Oh god, we split into cases. Wonderful.
B: So if , then for any nonzero we want , so we get .
A: For we get . So we are done with for now.
B: I think we are, though I have a feeling this was the easy part. So now let’s take a look at . If , then we easily see that there are solutions, so let .
A: Now we have , so we want . But we don’t know whether is a square or not!
B: It sometimes is and sometimes isn’t, I’m afraid, and sometimes it’s zero. We should figure out how many times is zero, square and nonsquare.
A: Clearly it’s zero for two values of . So now how often is a difference of squares a square or nonsquare… I think we might quickly get lost with all these squares; we should give some names to these numbers.
B: You have defined last piece of notation, so now it’s my turn. Let’s say is the number of solutons modulo to with and both quadratic residues, the number…
A: Why don’t you use squares and triangles?
B: Fine. is what I’ve said, is the same thing with residue and nonresidue and so on.
A: Now this is some notation I like!
B: Anyways, like we had with , this quite clearly only depends on being zero, a square or a nonsquare, so we can define and what not.
A: So now we have to figure out values of these numbers. Counting in and others we have 12 unknowns. There are some obvious relations between these numbers, like
B: Ones with should be easy to find. If we have , so , we see that, depending on modulo …
A: Can we please focus on just one case modulo for now? There are already enough numbers laying around.
B: Alright, for we see that is quadratic residue iff is, so from that we get
A: Also, if we consider all possible sums of quadratic residues, and on the other hand we count for all , we will find
so, as , dividing by we get
B: Also, similarly,
This looks like we’re getting somewhere. Hmm, when we were multiplying formulas by ratio of two squares or nonsquares, we could show that is the same for all squares or for all nonsquares . What if we tried to multiply by a ratio of a square and a nonsquare?
A: The result would be a nonsquare, so it’d flip the character of all terms… so this gives us another bijection! We have from this that swapping squares and triangles gives the same number! So for example, . But wait, plugging that into my last equation, we can see
B: Now this is real progress! So we can figure out all of . Now we have to relate these to other variables. Counting the solutions to equation with constrained worked before, so we can try restricting to be a square as well. If we take, say, to also be a residue and to be a nonresidue, then we easily get .
A: Note that we can rewrite as . But is a quadratic residue whenever is, so we can in essentially the same way see that the number of solutions is . So we must have
B: This is just what we needed! We can now figure out all the variables:
and the rest can be easily figured out by swapping squares and triangles.
A: We get quite similar results for :
B: You are incredibly fast at mental algebra I see.
A: Now that we have figured out these values, we can finally… what did we need these values for again?
B: We are given a square and we need to figure out for how many , in the equation the second summand is square or a nonsquare.
A: Ah, right. If , exactly for values of , so for values of , that summand has to be a square, which it can be in ways.
B: And for values of it has to be a nonsquare, which it can be in ways. So this gives…
A: Remember that also can be zero, and for two choices of we need !
B: Good point. In total, we get
A: We can deal with similarly, the only difference being that now can’t be , so we don’t get term. All in all,
B: Also, to recap, in this case we have
So we have a simultaneous recurrence involving three functions. How could we get around solving it?
A: Well, of course the hard part is actually figuring out what the answer possibly could be, since once we know the formula we will most likely be able to prove it inductively. One way to find the formula is to note that, if we denote by a vertical vector with entries , then above system of recurrences can be written as for certain matrix , so that . Hence we would like to find explicit formulas for the coefficients of the power of the matrix . Standard method for doing that in linear algebra is via diagonalization: we find an invertible matrix and a diagonal matrix such that . It is not always possible, but using eigenvalues and eigenvectors we can rather straightforwardly figure out that it is possible for , and indeed we can explicitly find . Usefulness of this approach is that now and taking powers of diagonal matrices is simple – you just take powers of the diagonal entries. This method is a very effective in practice, and in general it can…
B: Alright, enough of that rambling, what is the formula?
A: …as I was about to say, it gives us, for odd ,
and for even we have
B: That’s great! I suppose at this point we have achieved what we tried to achieve.
A: Not quite yet – we still have to work out. Thankfully, exactly the method works here, except now the sign changes for different values modulo . For respectively we have
B: I have no idea how you are doing these things in your head, but I’ll trust you it’s correct. This seems like a complete answer to our problem, at least modulo a prime.
A: You have reminded me – I’ve earlier found this one congruence for . I wonder how this big formula will look like reduced modulo : since we only deal with odd , the formula will simplify a bit. Also, we can use the Legendre symbol here – we can write , with sign iff .
B: Reducing this modulo , using Euler’s criterion we have
so, comparing with the earlier formula…
A: …we get
so setting, for example, …
B: …we find
with sign iff .
A: …so, we have just proven quadratic reciprocity. By playing around with your dumb game.
B: Please, let that be at the very least a proof that this game is not dumb. Alright, if you really don’t want to deal with it anymore then we can go do some public key exchange. What do you think?
A: Sounds great. I’ll go grab Eve, she really likes listening to our encrypted messages for some reason.
B: Alright. Catch you later.
The above proof is due to V.A. Lebesgue. I follow exposition from “The Quadratic Equation in Fp and the Quadratic Reciprocity Law” by R. Jakimczuk.
Originally I couldn’t make up my mind on whether I should follow this proof or the variation apparently due to W. Castryck (see his “A shortened classical proof of the quadratic reciprocity law”) which, instead of counting solutions to , counts solutions to the alternating sum equation for odd . Castryck’s proof is in pretty much every aspect simpler than Lebesgue’s, but has one drawback which would definitely discourage Bob from presenting it to Alice – the corresponding game is nearly trivial. The game which Bob has designed is definitely much more interesting and I encourage everyone reading this article to do what Alice didn’t want to do, namely figure out the winning strategy, possibly with the winning condition replaced by “the sum of squares is ” for some fixed , or even something more complex. Feel free to explore this game to your heart’s desire, generalizing to composite moduli, more complicated equations and what not. I don’t know if the gaming aspect of this theory has been explored before, but there is a beautiful and deep theory regarding the number of solutions of a given equation modulo various integers.
Last note: I am aware of the fact that the title of this post might be considered to be somewhat false advertisement, because throughout this article the only point at which we have used the game aspect is to motivate the question. I did try to find a proof of this theorem which would in more essential way use the game structure, for example encoding the Legendre symbol as the winning player, unfortunately to no avail. If anyone has any ideas on how to make this proof, or possibly some other proof of QR (I was thinking of Zolotarev’s proof, neatly explained in this article), more game-y, I’d certainly love to hear about that!
Post-last note: the form of this post might or might not have been subconciously inspired by this blog post by Adam P. Goucher, in which he explains Poncelet’s porism in the form of a Socratic dialogue.