This has been a week of asking and answering questions from emails, as far as I can see. I want to respond to two questions publicly, though, as they’ve some interesting value. So this is the first of a pair of blog posts. One is a short and sweet elementary proof of when 2 is a quadratic residue of a prime, responding to Moschops’s comments on an earlier blog post. But to continue my theme of some good and some bad, I’d also like to consider the latest “proof” of the Goldbach conjecture (which I’ll talk about in the next post tomorrow). More after the fold:

In the MSE question Legendre Symbol Second Supplementary Law from the user Yola, I gave a completely elementary answer. The question is to evaluate \left( \frac{2}{p} \right), where we are considering the Legendre Symbol. Moschops has asked me to clarify some of the steps, so let’s give a complete working.

We are assuming that p is an odd prime. Let s = (p-1)/2. Now consider the s different equations

1 = (-1)(-1)
2 = (2)(-1)^{2}
3 = (-3)(-1)^3
\dots
s = (\pm s)(-1)^s

where we choose the sign on s so that it multiplies with (-1)^s to give s. We want to multiply these s equations together. The left side is very easy to understand, and we just get s!. The right is a bit harder, as we have both numbers and signs. Let us first deal with the numbers, ignoring the (-1)^{\text{stuff}} terms. In particular, we have a positive 2, 4, 6, \dots, s and some negative odd numbers. In fact, if we think a bit harder, then because s = (p-1)/2, we’ll see that we have exactly half of the even numbers less than p.

Here’s the big trick. Note also that 2s \equiv -1 \mod p (so the largest even number less than p is the same as the smallest negative odd number), 2(s-1) \equiv -3 (the second largest even number less than p), and so on. Then we see that o0ur odd negative numbers are the same as the other half of the even numbers less than p. This is the big trick – the slick idea. This means that (-1)(2)(-3)(4) \dots (s) \equiv (2)(4)(6) \dots (p-3)(p-1) \equiv 2^s s! \mod p (to see this last equivalence, imagine that we associate each term of the factorial with one of the powers of two, so that we only get even factorial terms).

So we have evaluated the “numbers” portion of the product of the right hand side. We still need to consider the “signs” portion, i.e. the product of the (-1)^{\text{stuff}} terms. This is not so bad, as (-1)^{1 + 2 + \dots + s} = (-1)^{s(s+1)/2}. So the complete product of the RHS terms is 2^s s! (-1)^{s(s+1)/2} and the product of the LHS is s! (all done mod p).

Thus we are left with 2^s \equiv (-1)^{s(s+1)/2} = (-1)^{(p^2-1)/8}, which is the standard rule. Many thanks to Moschops for the question – I hope this helps. At least now we have a clear comment thread for questions.

Advertisements