An elementary proof of when 2 is a quadratic residue

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 $latex 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 $latex \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 $latex p$ is an odd prime. Let $latex s = (p-1)/2$. Now consider the $latex s$ different equations

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

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

Here’s the big trick. Note also that $latex 2s \equiv -1 \mod p$ (so the largest even number less than $latex p$ is the same as the smallest negative odd number), $latex 2(s-1) \equiv -3$ (the second largest even number less than $latex 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 $latex p$. This is the big trick – the slick idea. This means that $latex (-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 $latex (-1)^{\text{stuff}}$ terms. This is not so bad, as $latex (-1)^{1 + 2 + \dots + s} = (-1)^{s(s+1)/2}$. So the complete product of the RHS terms is $latex 2^s s! (-1)^{s(s+1)/2}$ and the product of the LHS is $latex s!$ (all done mod $latex p$).

Thus we are left with $latex 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.

This entry was posted in Expository, Math.NT, Mathematics, SE and tagged , , , , , , , , , . Bookmark the permalink.

7 Responses to An elementary proof of when 2 is a quadratic residue

  1. Moschops says:

    Many thanks for your efforts. I will work on the above and place it into my scrawlings. If I understand this correctly in its context, this is the final part of the proof that $latex 2^{(p-1)/2} equiv (-1)^{((p^2) -1)/8)}$ (mod p), and we know from other means (that I have yet to prove – it’s the final part I’m missing, I think) that this is 1 (mod p) if 2 is a quadratic residue of p and is -1 (mod p) if 2 is not a quadratic residue, and we can then show that p must be +1 or -1 mod 8 to get a result of +1.

    I hope that’s right; I have as much (and often more) trouble interpreting the theorems on number than I do proving them. This just leaves me to prove that $latex 2^s$ is a value indicating quadratic reciprocity (in the textbook I’m struggling through, Apostol’s Introduction to Analytic Number Theory, the values of +1 and -1 meaning “is a quadratic residue” and “is not a quadratic residue” are presented at first, without justification, as arbitrary values, which has caused me no end of trouble in understanding).

    Your help much appreciated. I think I’m now less than a day or so from my target (that is, “given x^2 congruent to 2 mod p, what are the possible values of p?”).

    • mixedmath says:

      The missing part, what you say we know from other means, is something known as Euler’s Criterion (wiki), which in short says that $latex a^{(p-1)/2} equiv left(frac{1}{p}right)$. I had taken this as known, as it’s the only really easy way to calculate when something is a quadratic residue.

      And yes, you are incredibly close to knowing the answer to your target.

      • Moschops says:

        I have more :(
        LHS = RHS
        s! = (2^s) s! (-1)^(s(s+1)/2)
        1 = (2^s) (-1)^(s(s+1)/2)
        I can’t get from here to
        (2^s) = (-1)^(s(s+1)/2)
        I’m terrible at this.

    • mixedmath says:

      Ok. So you wonder about getting from $latex 1 = (2^s) (-1)^{s(s+1)/2}$ to $latex 2^s = (-1)^{s(s+1)/2}$. This is a perhaps deceptive step. Sometimes with these sorts of equations, you should compare what’s different between the two equations and see if you can justify it. But to get there here:

      Divide both sides by $latex (-1)^{s(s+1)/2}$ and realize that $latex frac{1}{-1} = -1$ so that we can keep a positive exponent. Rather, $latex (-1)^n = (-1)^{-n}$ for all $latex n$.

      • Moschops says:

        That’s clever. Thanks very much. I am now getting pretty close to solving this one-mark, easy-intro-to-the-rest-of-the-question section. I think it’s supposed to take about sixty seconds. I’m up to a week :p

  2. Pingback: The danger of confusing cosets and numbers « mixedmath

Leave a Reply