Quadratic Reciprocity proof -- Number Theory 23

If you are going to use an ad-blocker, considering using brave and tipping me BAT!

Books I like:

Abstract Algebra:

Differential Forms:

Number Theory:

Analysis:

Calculus:

My Filming Equipment:

[allenminch]

I'm blown away by the logical beauty of this proof...

[MathFromAlphaToOmega]

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.

[ianparrish]

I think at 6:18 you meant for all i, j rather than for all i=j.

[noahtaul]

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) = =

= ((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).

[Musiclover]

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.

[mihaipuiu]

I like more this new proof. b/c it's easier to understand. Thank you, Michael!

[laurendoe]

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.

[celestialmath]

Hi, big fan!! How about making a video about the Herschfeld’s Convergence
Theorem and it's proof? It's very confusing, Thank You !!

[anonimmors]

Thank you I had to learn this proof by Eisenstein XD but this is much better

[conanedojawa]

27:53 can anyone help me with this homework i couldn't solve it by myself please

[synaestheziac]

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!