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).
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.
Leave a comment
Info on how to comment
To make a comment, please send an email using the button below. Your email address won't be shared (unless you include it in the body of your comment). If you don't want your real name to be used next to your comment, please specify the name you would like to use. If you want your name to link to a particular url, include that as well.
bold, italics, and plain text are allowed in
comments. A reasonable subset of markdown is supported, including lists,
links, and fenced code blocks. In addition, math can be formatted using
$(inline math)$ or $$(your display equation)$$.
Please use plaintext email when commenting. See Plaintext Email and Comments on this site for more. Note also that comments are expected to be open, considerate, and respectful.
Comments (6)
2012-08-23 Moschops
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 $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 $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?").
2012-08-23 davidlowryduda
The missing part, what you say we know from other means, is something known as Euler's Criterion (wiki), which in short says that $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.
2012-08-27 Moschops
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.
2012-08-28 davidlowryduda
Ok. So you wonder about getting from $1 = (2^s) (-1)^{s(s+1)/2}$ to $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 $(-1)^{s(s+1)/2}$ and realize that $\frac{1}{-1} = -1$ so that we can keep a positive exponent. Rather, $(-1)^n = (-1)^{-n}$ for all $n$.
2012-08-28 Moschops
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
2012-08-28 davidlowryduda
Good luck!