A different proof of quadratic reciprocity I saw that I like, because it can be reduced to one thought, while the rest is just carrying it out: "Given the units mod pq, modded out by the subgroup {±1}, find the product of all elements in two different ways." The details: Let G be the group described above, that is, G={i∈{1, 2, ... pq}: (i, pq)=1}/{±1}, we can choose representatives for all elements in the quotient in 2 ways. For each way, we use the Chinese Remainder Theorem to write the elements mod p and mod q, and compute the product of all representatives that way, and compare the results. Way 1: The elements of G can be represented by the elements of {1, 2, ... (pq-1)/2} that are relatively prime to p and q. Mod p, this set consists of (q-1)/2 full copies of the set {1, ... p-1}, along with a half-set {1, ..., (p-1)/2}. EXCEPT we have to exclude q, 2q, ... and (p-1)/2*q. So the product of this set mod p is ((p-1)!)^(q-1)/2 * ((p-1)/2)! / (((p-1)/2)! * q^((p-1)/2)) = (-1)^(q-1)/2 / (q/p) = (-1)^(q-1)/2*(q/p). (Here we used Wilson's theorem to write (p-1)!=-1 mod p, and we used the fact that (q/p) is either 1 or -1, so dividing by (q/p) is the same as multiplying by (q/p).) A similar calculation exists mod q. So we get the product is ((-1)^(q-1)/2 * (q/p) mod p, (-1)^(p-1)/2 * (p/q) mod q). Way 2: The elements of G can be represented by the elements of {1, 2, ... pq-1} that are relatively prime to p and are less than q/2 mod q. That is, those numbers that are in {1, 2, ... p-1} mod p and in {1, 2, ... (q-1)/2} mod q. Mod p, the product with these representatives consists of (q-1)/2 full copies of (p-1)!, and mod q it consists of (p-1) copies of ((q-1)/2)!. By Wilson's theorem, we know that mod p it gives (-1)^(q-1)/2. We can finagle the ((q-1)/2)! ^ (p-1) a bit too: (((q-1)/2)!)^(p-1) = ((1*2*3*...*(q-1)/2)*((q-1)/2*...*2*1))^(p-1)/2 = (1*2*3*...*(q-1)/2*(q+1)/2*...*(q-1)*(-1)^(q-1)/2)^(p-1)/2 = ((q-1)!)^(p-1)/2 * (-1)^((q-1)(p-1)/4) = (-1)^(p-1)/2 * (-1)^((q-1)(p-1))/4. So the product of the elements of G with these representatives is ((-1)^(q-1)/2 mod p, (-1)^(p-1)/2 * (-1)^((q-1)(p-1))/4 mod q). Conclusion: So we know that ((-1)^(q-1)/2 * (q/p) mod p, (-1)^(p-1)/2 * (p/q) mod q) = ((-1)^(q-1)/2 mod p, (-1)^(p-1)/2 * (-1)^((q-1)(p-1))/4 mod q), up to {(1, 1), (-1, -1)}. If s is the sign we need to make them actually equal, since everything is just powers of -1 and therefore congruence mod p or q means equality, we get: (-1)^(q-1)/2 * (q/p) = s*(-1)^(q-1)/2 so (q/p)=s and (-1)^(p-1)/2 * (p/q) = s*(-1)^(p-1)/2 * (-1)^((q-1)(p-1))/4, or (p/q) = (q/p)*(-1)^((q-1)(p-1))/4. We can move (q/p) to the other side, and obtain the statement of quadratic reciprocity (p/q)(q/p)=(-1)^((p-1)/2 * (q-1)/2).
@@rockinroggenrola7277 I think Michael’s proof was a little more enlightening, but I think the most enlightening proof is the one that uses Gauss sums. Once you learn a couple simple lemmas about Gauss sums, the proof is essentially a single line. It establishes a deep connection between field extensions, and the method can be generalized to Jacobi sums and others.
@@JM-us3fr I'll definitely look into this proof you're talking about. I started studying number theory recently, and up to this point, it's been pretty easy, but I got confused after getting up to quadratic reciprocity.
@@rockinroggenrola7277 Well even if the proof/proofs of Quadratic Reciprocity is/are confusing, just remember the essence of the result. It’s about a correspondence between quadratic residues modulo p and quadratic residues modulo q. Typically (p|q)=(q|p), but if p and q are 3 mod 4, then (p|q)=-(q|p). This can be useful when you are looking for integer solutions to an equation of the form x^2=stuff. If ‘stuff’ isn’t a quadratic residue modulo even a single p, then there can’t be any solutions.
I really like the proof using Gauss sums - with a few preliminary lemmas, the proof boils down to essentially just one line. If you have plans to go deeper into number theory, Gauss sums and roots of unity in general could be interesting to look at.
Great lecture series. I am from engineering background and trying to learn number theory to support my interests in cryptography. Quick question, referring to the statement of Gauss's Lemma at 1:54 min. In the third line, should it be just "residues" instead of "quadratic residues"? I was a little thrown off initially, but listening to the proof part further down (and also cross checking with Gauss's Lemma in wikipedia) I made this inference. Will appreciate your advice. Thanks.
I SO wanted to watch this video.... but it went so over my head by 1:30 that I had to admit that continuing to watch would only go even farther over my head.
How do we show that (p^2 - 1)/8 is natural for all odd primes p? I’m guessing it’s something we’re supposed to know how to do at this point in the course, but I’m stuck!
Okay I think I figured it out: p must be congruent to 1, 3, 5, or 7 mod 8, so p^2 must be congruent to 1, 9, 25, or 49 mod 8, all of which reduce to 1, so p^2 - 1 is congruent to 0 mod 8. Is that correct?
Actually, p^2 ≡ 1 (mod 8) for all odd p, not just odd prime p. Working mod 8 has only 3 quadratic residues, 0 or 4 for even numbers, and 1 for odd numbers. If you let p = (2n + 1), then p^2 = 4n^2 + 4n + 1, so (p^2 - 1) = 4n^2 + 4n = 4n(n+1). Since either n or (n+1) is even, 4n(n+1) must be divisible by 8.
If you think about how multiples of 4 are distributed, it should be clear that either p-1 or p+1 is divisible by 4. Thus, p^2-1=(p-1)(p+1) must be divisible by 8.
I'm blown away by the logical beauty of this proof...
A different proof of quadratic reciprocity I saw that I like, because it can be reduced to one thought, while the rest is just carrying it out: "Given the units mod pq, modded out by the subgroup {±1}, find the product of all elements in two different ways."
The details: Let G be the group described above, that is, G={i∈{1, 2, ... pq}: (i, pq)=1}/{±1}, we can choose representatives for all elements in the quotient in 2 ways. For each way, we use the Chinese Remainder Theorem to write the elements mod p and mod q, and compute the product of all representatives that way, and compare the results.
Way 1: The elements of G can be represented by the elements of {1, 2, ... (pq-1)/2} that are relatively prime to p and q. Mod p, this set consists of (q-1)/2 full copies of the set {1, ... p-1}, along with a half-set {1, ..., (p-1)/2}. EXCEPT we have to exclude q, 2q, ... and (p-1)/2*q. So the product of this set mod p is
((p-1)!)^(q-1)/2 * ((p-1)/2)! / (((p-1)/2)! * q^((p-1)/2)) = (-1)^(q-1)/2 / (q/p) = (-1)^(q-1)/2*(q/p).
(Here we used Wilson's theorem to write (p-1)!=-1 mod p, and we used the fact that (q/p) is either 1 or -1, so dividing by (q/p) is the same as multiplying by (q/p).) A similar calculation exists mod q. So we get the product is ((-1)^(q-1)/2 * (q/p) mod p, (-1)^(p-1)/2 * (p/q) mod q).
Way 2: The elements of G can be represented by the elements of {1, 2, ... pq-1} that are relatively prime to p and are less than q/2 mod q. That is, those numbers that are in {1, 2, ... p-1} mod p and in {1, 2, ... (q-1)/2} mod q. Mod p, the product with these representatives consists of (q-1)/2 full copies of (p-1)!, and mod q it consists of (p-1) copies of ((q-1)/2)!. By Wilson's theorem, we know that mod p it gives (-1)^(q-1)/2. We can finagle the ((q-1)/2)! ^ (p-1) a bit too:
(((q-1)/2)!)^(p-1) = ((1*2*3*...*(q-1)/2)*((q-1)/2*...*2*1))^(p-1)/2 = (1*2*3*...*(q-1)/2*(q+1)/2*...*(q-1)*(-1)^(q-1)/2)^(p-1)/2
= ((q-1)!)^(p-1)/2 * (-1)^((q-1)(p-1)/4) = (-1)^(p-1)/2 * (-1)^((q-1)(p-1))/4.
So the product of the elements of G with these representatives is ((-1)^(q-1)/2 mod p, (-1)^(p-1)/2 * (-1)^((q-1)(p-1))/4 mod q).
Conclusion: So we know that ((-1)^(q-1)/2 * (q/p) mod p, (-1)^(p-1)/2 * (p/q) mod q) = ((-1)^(q-1)/2 mod p, (-1)^(p-1)/2 * (-1)^((q-1)(p-1))/4 mod q), up to {(1, 1), (-1, -1)}. If s is the sign we need to make them actually equal, since everything is just powers of -1 and therefore congruence mod p or q means equality, we get:
(-1)^(q-1)/2 * (q/p) = s*(-1)^(q-1)/2 so (q/p)=s
and
(-1)^(p-1)/2 * (p/q) = s*(-1)^(p-1)/2 * (-1)^((q-1)(p-1))/4, or (p/q) = (q/p)*(-1)^((q-1)(p-1))/4.
We can move (q/p) to the other side, and obtain the statement of quadratic reciprocity (p/q)(q/p)=(-1)^((p-1)/2 * (q-1)/2).
I think this is probably the most elementary of all the proofs, but it’s not particularly enlightening.
@@JM-us3fr Personally, I don't find the other proofs I've seen of quadratic reciprocity including the one in this video enlightening either.
@@rockinroggenrola7277 I think Michael’s proof was a little more enlightening, but I think the most enlightening proof is the one that uses Gauss sums. Once you learn a couple simple lemmas about Gauss sums, the proof is essentially a single line. It establishes a deep connection between field extensions, and the method can be generalized to Jacobi sums and others.
@@JM-us3fr I'll definitely look into this proof you're talking about. I started studying number theory recently, and up to this point, it's been pretty easy, but I got confused after getting up to quadratic reciprocity.
@@rockinroggenrola7277 Well even if the proof/proofs of Quadratic Reciprocity is/are confusing, just remember the essence of the result. It’s about a correspondence between quadratic residues modulo p and quadratic residues modulo q. Typically (p|q)=(q|p), but if p and q are 3 mod 4, then (p|q)=-(q|p).
This can be useful when you are looking for integer solutions to an equation of the form x^2=stuff. If ‘stuff’ isn’t a quadratic residue modulo even a single p, then there can’t be any solutions.
I really like the proof using Gauss sums - with a few preliminary lemmas, the proof boils down to essentially just one line. If you have plans to go deeper into number theory, Gauss sums and roots of unity in general could be interesting to look at.
I agree, that is perhaps the most enlightening proof.
Very clean and fast proof!
Great lecture series. I am from engineering background and trying to learn number theory to support my interests in cryptography. Quick question, referring to the statement of Gauss's Lemma at 1:54 min. In the third line, should it be just "residues" instead of "quadratic residues"? I was a little thrown off initially, but listening to the proof part further down (and also cross checking with Gauss's Lemma in wikipedia) I made this inference. Will appreciate your advice. Thanks.
I like more this new proof. b/c it's easier to understand. Thank you, Michael!
I think at 6:18 you meant for all i, j rather than for all i=j.
41:01
I SO wanted to watch this video.... but it went so over my head by 1:30 that I had to admit that continuing to watch would only go even farther over my head.
Thank you I had to learn this proof by Eisenstein XD but this is much better
Hi, big fan!! How about making a video about the Herschfeld’s Convergence
Theorem and it's proof? It's very confusing, Thank You !!
How do we show that (p^2 - 1)/8 is natural for all odd primes p? I’m guessing it’s something we’re supposed to know how to do at this point in the course, but I’m stuck!
Okay I think I figured it out: p must be congruent to 1, 3, 5, or 7 mod 8, so p^2 must be congruent to 1, 9, 25, or 49 mod 8, all of which reduce to 1, so p^2 - 1 is congruent to 0 mod 8. Is that correct?
@@synaestheziac Correct!
You can also do it just using arithmetic, by the fact that p = 2k+1 for some k>=1.
Actually, p^2 ≡ 1 (mod 8) for all odd p, not just odd prime p. Working mod 8 has only 3 quadratic residues, 0 or 4 for even numbers, and 1 for odd numbers.
If you let p = (2n + 1), then p^2 = 4n^2 + 4n + 1, so (p^2 - 1) = 4n^2 + 4n = 4n(n+1). Since either n or (n+1) is even, 4n(n+1) must be divisible by 8.
If you think about how multiples of 4 are distributed, it should be clear that either p-1 or p+1 is divisible by 4. Thus, p^2-1=(p-1)(p+1) must be divisible by 8.
27:53 can anyone help me with this homework i couldn't solve it by myself please
Wowww ,