Skip to main content
added 48 characters in body
Source Link
Martin Sleziak
  • 4.7k
  • 4
  • 35
  • 40

I think by far the simplest easiest to remember elementary proof of QR is due to Rousseau (On the quadratic reciprocity lawOn the quadratic reciprocity law). All it uses is the Chinese remainder theorem and Euler's formula $a^{(p-1)/2}\equiv (\frac{a}{p}) \mod p$. The mathscinet review does a very good job of outlining the proof. I'll try to explain how I remember it here (but the lack of formatting is really rough for this argument).

Here's the outline. Consider $(\mathbb{Z}/p)^\times \times (\mathbb{Z}/q)^\times = (\mathbb{Z}/pq)^\times$. We want to split that group in "half", that is consider a subset such that exactly one of $x$ and $-x$ is in it. There are three obvious ways to do that. For each of these we take the product of all the elements in that "half." The resulting three numbers are equal up to an overall sign. Calculating that sign on the $(\mathbb{Z}/p)^\times$ part and the $(\mathbb{Z}/q)^\times$ part give you the two sides of QR.

In more detail. First let me describe the three "obvious" halves:

  1. Take the first half of $(\mathbb{Z}/p)^\times$ and all of the other factor.
  2. Take all of the first factor and the first half of $(\mathbb{Z}/q)^\times$.
  3. Take the first half of $(\mathbb{Z}/pq)^\times$.

The three products are then (letting $P = (p-1)/2$ and $Q=(q-1)/2$):

  1. $(P!^{q-1}, (q-1)!^P)$.
  2. $((p-1)!^Q, Q!^{p-1})$.
  3. $\left(\dfrac{(p-1)!^Q P!}{q^P P!},\dfrac{(q-1)!^P Q!}{p^Q Q!}\right)$.

All of these are equal to each other up to overall signs. Looking at the second component it's clear that the sign relating 1 and 3 is $\left(\frac{p}{q}\right)$. Similarly, the sign relating 2 and 3 is $\left(\frac{q}{p}\right)$. So the sign relating 1 and 2 is $\left(\frac{p}{q}\right) \left(\frac{q}{p}\right)$. But to get from 1 to 2 we just changed the signs of $\frac{p-1}{2} \frac{q-1}{2}$ elements. QED

I think by far the simplest easiest to remember elementary proof of QR is due to Rousseau (On the quadratic reciprocity law). All it uses is the Chinese remainder theorem and Euler's formula $a^{(p-1)/2}\equiv (\frac{a}{p}) \mod p$. The mathscinet review does a very good job of outlining the proof. I'll try to explain how I remember it here (but the lack of formatting is really rough for this argument).

Here's the outline. Consider $(\mathbb{Z}/p)^\times \times (\mathbb{Z}/q)^\times = (\mathbb{Z}/pq)^\times$. We want to split that group in "half", that is consider a subset such that exactly one of $x$ and $-x$ is in it. There are three obvious ways to do that. For each of these we take the product of all the elements in that "half." The resulting three numbers are equal up to an overall sign. Calculating that sign on the $(\mathbb{Z}/p)^\times$ part and the $(\mathbb{Z}/q)^\times$ part give you the two sides of QR.

In more detail. First let me describe the three "obvious" halves:

  1. Take the first half of $(\mathbb{Z}/p)^\times$ and all of the other factor.
  2. Take all of the first factor and the first half of $(\mathbb{Z}/q)^\times$.
  3. Take the first half of $(\mathbb{Z}/pq)^\times$.

The three products are then (letting $P = (p-1)/2$ and $Q=(q-1)/2$):

  1. $(P!^{q-1}, (q-1)!^P)$.
  2. $((p-1)!^Q, Q!^{p-1})$.
  3. $\left(\dfrac{(p-1)!^Q P!}{q^P P!},\dfrac{(q-1)!^P Q!}{p^Q Q!}\right)$.

All of these are equal to each other up to overall signs. Looking at the second component it's clear that the sign relating 1 and 3 is $\left(\frac{p}{q}\right)$. Similarly, the sign relating 2 and 3 is $\left(\frac{q}{p}\right)$. So the sign relating 1 and 2 is $\left(\frac{p}{q}\right) \left(\frac{q}{p}\right)$. But to get from 1 to 2 we just changed the signs of $\frac{p-1}{2} \frac{q-1}{2}$ elements. QED

I think by far the simplest easiest to remember elementary proof of QR is due to Rousseau (On the quadratic reciprocity law). All it uses is the Chinese remainder theorem and Euler's formula $a^{(p-1)/2}\equiv (\frac{a}{p}) \mod p$. The mathscinet review does a very good job of outlining the proof. I'll try to explain how I remember it here (but the lack of formatting is really rough for this argument).

Here's the outline. Consider $(\mathbb{Z}/p)^\times \times (\mathbb{Z}/q)^\times = (\mathbb{Z}/pq)^\times$. We want to split that group in "half", that is consider a subset such that exactly one of $x$ and $-x$ is in it. There are three obvious ways to do that. For each of these we take the product of all the elements in that "half." The resulting three numbers are equal up to an overall sign. Calculating that sign on the $(\mathbb{Z}/p)^\times$ part and the $(\mathbb{Z}/q)^\times$ part give you the two sides of QR.

In more detail. First let me describe the three "obvious" halves:

  1. Take the first half of $(\mathbb{Z}/p)^\times$ and all of the other factor.
  2. Take all of the first factor and the first half of $(\mathbb{Z}/q)^\times$.
  3. Take the first half of $(\mathbb{Z}/pq)^\times$.

The three products are then (letting $P = (p-1)/2$ and $Q=(q-1)/2$):

  1. $(P!^{q-1}, (q-1)!^P)$.
  2. $((p-1)!^Q, Q!^{p-1})$.
  3. $\left(\dfrac{(p-1)!^Q P!}{q^P P!},\dfrac{(q-1)!^P Q!}{p^Q Q!}\right)$.

All of these are equal to each other up to overall signs. Looking at the second component it's clear that the sign relating 1 and 3 is $\left(\frac{p}{q}\right)$. Similarly, the sign relating 2 and 3 is $\left(\frac{q}{p}\right)$. So the sign relating 1 and 2 is $\left(\frac{p}{q}\right) \left(\frac{q}{p}\right)$. But to get from 1 to 2 we just changed the signs of $\frac{p-1}{2} \frac{q-1}{2}$ elements. QED

Finishing TeXing while this is on the front page
Source Link
LSpice
  • 12.9k
  • 4
  • 45
  • 69

I think by far the simplest easiest to remember elementary proof of QR is due to Rousseau (RousseauOn the quadratic reciprocity law). All it uses is the Chinese remainder theorem and Euler's formula $a^{(p-1)/2}\equiv (\frac{a}{p}) \mod p$. The mathscinet review does a very good job of outlining the proof. I'll try to explain how I remember it here (but the lack of formatting is really rough for this argument).

Here's the outline. Consider $(\mathbb{Z}/p)^\times \times (\mathbb{Z}/q)^\times = (\mathbb{Z}/pq)^\times$. We want to split that group in "half", that is consider a subset such that exactly one of x$x$ and -x$-x$ is in it. There are three obvious ways to do that. For each of these we take the product of all the elements in that "half." The resulting three numbers are equal up to an overall sign. Calculating that sign on the $(\mathbb{Z}/p)^\times$ part and the $(\mathbb{Z}/q)^\times$ part give you the two sides of QR.

In more detail. First let me describe the three "obvious" halves:

  1. Take the first half of $(\mathbb{Z}/p)^\times$ and all of the other factor.
  2. Take all of the first factor and the first half of $(\mathbb{Z}/q)^\times$.
  3. Take the first half of $(\mathbb{Z}/pq)^\times$.

The three products are then (letting P = (p-1)/2$P = (p-1)/2$ and Q=(q-1)/2$Q=(q-1)/2$):

  1. $(P!^{q-1}, (q-1)!^P)$.
  2. $((p-1)!^Q, Q!^{p-1})$.
  3. $\left(\frac{(p-1)!^Q P!}{q^P P!},\frac{(q-1)!^P Q!}{p^Q Q!}\right)$$\left(\dfrac{(p-1)!^Q P!}{q^P P!},\dfrac{(q-1)!^P Q!}{p^Q Q!}\right)$.

All of these are equal to each other up to overall signs. Looking at the second component it's clear that the sign relating 1 and 3 is $\left(\frac{p}{q}\right)$. Similarly, the sign relating 2 and 3 is $\left(\frac{q}{p}\right)$. So the sign relating 1 and 2 is $\left(\frac{p}{q}\right) \left(\frac{q}{p}\right)$. But to get from 1 to 2 we just changed the signs of $\frac{p-1}{2} \frac{q-1}{2}$ elements. QED

I think by far the simplest easiest to remember elementary proof of QR is due to Rousseau. All it uses is the Chinese remainder theorem and Euler's formula $a^{(p-1)/2}\equiv (\frac{a}{p}) \mod p$. The mathscinet review does a very good job of outlining the proof. I'll try to explain how I remember it here (but the lack of formatting is really rough for this argument).

Here's the outline. Consider $(\mathbb{Z}/p)^\times \times (\mathbb{Z}/q)^\times = (\mathbb{Z}/pq)^\times$. We want to split that group in "half", that is consider a subset such that exactly one of x and -x is in it. There are three obvious ways to do that. For each of these we take the product of all the elements in that "half." The resulting three numbers are equal up to an overall sign. Calculating that sign on the $(\mathbb{Z}/p)^\times$ part and the $(\mathbb{Z}/q)^\times$ part give you the two sides of QR.

In more detail. First let me describe the three "obvious" halves:

  1. Take the first half of $(\mathbb{Z}/p)^\times$ and all of the other factor
  2. Take all of the first factor and the first half of $(\mathbb{Z}/q)^\times$
  3. Take the first half of $(\mathbb{Z}/pq)^\times$

The three products are then (letting P = (p-1)/2 and Q=(q-1)/2):

  1. $(P!^{q-1}, (q-1)!^P)$
  2. $((p-1)!^Q, Q!^{p-1})$
  3. $\left(\frac{(p-1)!^Q P!}{q^P P!},\frac{(q-1)!^P Q!}{p^Q Q!}\right)$

All of these are equal to each other up to overall signs. Looking at the second component it's clear that the sign relating 1 and 3 is $\left(\frac{p}{q}\right)$. Similarly, the sign relating 2 and 3 is $\left(\frac{q}{p}\right)$. So the sign relating 1 and 2 is $\left(\frac{p}{q}\right) \left(\frac{q}{p}\right)$. But to get from 1 to 2 we just changed the signs of $\frac{p-1}{2} \frac{q-1}{2}$ elements. QED

I think by far the simplest easiest to remember elementary proof of QR is due to Rousseau (On the quadratic reciprocity law). All it uses is the Chinese remainder theorem and Euler's formula $a^{(p-1)/2}\equiv (\frac{a}{p}) \mod p$. The mathscinet review does a very good job of outlining the proof. I'll try to explain how I remember it here (but the lack of formatting is really rough for this argument).

Here's the outline. Consider $(\mathbb{Z}/p)^\times \times (\mathbb{Z}/q)^\times = (\mathbb{Z}/pq)^\times$. We want to split that group in "half", that is consider a subset such that exactly one of $x$ and $-x$ is in it. There are three obvious ways to do that. For each of these we take the product of all the elements in that "half." The resulting three numbers are equal up to an overall sign. Calculating that sign on the $(\mathbb{Z}/p)^\times$ part and the $(\mathbb{Z}/q)^\times$ part give you the two sides of QR.

In more detail. First let me describe the three "obvious" halves:

  1. Take the first half of $(\mathbb{Z}/p)^\times$ and all of the other factor.
  2. Take all of the first factor and the first half of $(\mathbb{Z}/q)^\times$.
  3. Take the first half of $(\mathbb{Z}/pq)^\times$.

The three products are then (letting $P = (p-1)/2$ and $Q=(q-1)/2$):

  1. $(P!^{q-1}, (q-1)!^P)$.
  2. $((p-1)!^Q, Q!^{p-1})$.
  3. $\left(\dfrac{(p-1)!^Q P!}{q^P P!},\dfrac{(q-1)!^P Q!}{p^Q Q!}\right)$.

All of these are equal to each other up to overall signs. Looking at the second component it's clear that the sign relating 1 and 3 is $\left(\frac{p}{q}\right)$. Similarly, the sign relating 2 and 3 is $\left(\frac{q}{p}\right)$. So the sign relating 1 and 2 is $\left(\frac{p}{q}\right) \left(\frac{q}{p}\right)$. But to get from 1 to 2 we just changed the signs of $\frac{p-1}{2} \frac{q-1}{2}$ elements. QED

added 17 characters in body
Source Link
Noah Snyder
  • 28.1k
  • 4
  • 94
  • 170

I think by far the simplest easiest to remember elementary proof of QR is due to RousseauRousseau. All it uses is the Chinese remainder theorem and Euler's formula $a^{(p-1)/2}\equiv (\frac{a}{p}) \mod p$. The mathscinet review does a very good job of outlining the proof. I'll try to explain how I remember it here (but the lack of formatting is really rough for this argument).

Here's the outline. Consider $(\mathbb{Z}/p)^\times \times (\mathbb{Z}/q)^\times = (\mathbb{Z}/pq)^\times$. We want to split that group in "half", that is consider a subset such that exactly one of x and -x is in it. There are three obvious ways to do that. For each of these we take the product of all the elements in that "half." The resulting three numbers are equal up to an overall sign. Calculating that sign on the $(\mathbb{Z}/p)^\times$ part and the $(\mathbb{Z}/q)^\times$ part give you the two sides of QR.

In more detail. First let me describe the three "obvious" halves:

  1. Take the first half of $(\mathbb{Z}/p)^\times$ and all of the other factor
  2. Take all of the first factor and the first half of $(\mathbb{Z}/q)^\times$
  3. Take the first half of $(\mathbb{Z}/pq)^\times$

The three products are then (letting P = (p-1)/2 and Q=(q-1)/2):

  1. $(P!^{q-1}, (q-1)!^P)$
  2. $((p-1)!^Q, Q!^{p-1})$
  3. $\left(\frac{(p-1)!^Q P!}{q^P P!},\frac{(q-1)!^P Q!}{p^Q Q!}\right)$

All of these are equal to each other up to overall signs. Looking at the second component it's clear that the sign relating 1 and 3 is $\left(\frac{p}{q}\right)$. Similarly, the sign relating 2 and 3 is $\left(\frac{q}{p}\right)$. So the sign relating 1 and 2 is $\left(\frac{p}{q}\right) \left(\frac{q}{p}\right)$. But to get from 1 to 2 we just changed the signs of $\frac{p-1}{2} \frac{q-1}{2}$ elements. QED

I think by far the simplest easiest to remember elementary proof of QR is due to Rousseau. All it uses is the Chinese remainder theorem and Euler's formula $a^{(p-1)/2}\equiv (\frac{a}{p}) \mod p$. The mathscinet review does a very good job of outlining the proof. I'll try to explain how I remember it here (but the lack of formatting is really rough for this argument).

Here's the outline. Consider $(\mathbb{Z}/p)^\times \times (\mathbb{Z}/q)^\times = (\mathbb{Z}/pq)^\times$. We want to split that group in "half", that is consider a subset such that exactly one of x and -x is in it. There are three obvious ways to do that. For each of these we take the product of all the elements in that "half." The resulting three numbers are equal up to an overall sign. Calculating that sign on the $(\mathbb{Z}/p)^\times$ part and the $(\mathbb{Z}/q)^\times$ part give you the two sides of QR.

In more detail. First let me describe the three "obvious" halves:

  1. Take the first half of $(\mathbb{Z}/p)^\times$ and all of the other factor
  2. Take all of the first factor and the first half of $(\mathbb{Z}/q)^\times$
  3. Take the first half of $(\mathbb{Z}/pq)^\times$

The three products are then (letting P = (p-1)/2 and Q=(q-1)/2):

  1. $(P!^{q-1}, (q-1)!^P)$
  2. $((p-1)!^Q, Q!^{p-1})$
  3. $\left(\frac{(p-1)!^Q P!}{q^P P!},\frac{(q-1)!^P Q!}{p^Q Q!}\right)$

All of these are equal to each other up to overall signs. Looking at the second component it's clear that the sign relating 1 and 3 is $\left(\frac{p}{q}\right)$. Similarly, the sign relating 2 and 3 is $\left(\frac{q}{p}\right)$. So the sign relating 1 and 2 is $\left(\frac{p}{q}\right) \left(\frac{q}{p}\right)$. But to get from 1 to 2 we just changed the signs of $\frac{p-1}{2} \frac{q-1}{2}$ elements. QED

I think by far the simplest easiest to remember elementary proof of QR is due to Rousseau. All it uses is the Chinese remainder theorem and Euler's formula $a^{(p-1)/2}\equiv (\frac{a}{p}) \mod p$. The mathscinet review does a very good job of outlining the proof. I'll try to explain how I remember it here (but the lack of formatting is really rough for this argument).

Here's the outline. Consider $(\mathbb{Z}/p)^\times \times (\mathbb{Z}/q)^\times = (\mathbb{Z}/pq)^\times$. We want to split that group in "half", that is consider a subset such that exactly one of x and -x is in it. There are three obvious ways to do that. For each of these we take the product of all the elements in that "half." The resulting three numbers are equal up to an overall sign. Calculating that sign on the $(\mathbb{Z}/p)^\times$ part and the $(\mathbb{Z}/q)^\times$ part give you the two sides of QR.

In more detail. First let me describe the three "obvious" halves:

  1. Take the first half of $(\mathbb{Z}/p)^\times$ and all of the other factor
  2. Take all of the first factor and the first half of $(\mathbb{Z}/q)^\times$
  3. Take the first half of $(\mathbb{Z}/pq)^\times$

The three products are then (letting P = (p-1)/2 and Q=(q-1)/2):

  1. $(P!^{q-1}, (q-1)!^P)$
  2. $((p-1)!^Q, Q!^{p-1})$
  3. $\left(\frac{(p-1)!^Q P!}{q^P P!},\frac{(q-1)!^P Q!}{p^Q Q!}\right)$

All of these are equal to each other up to overall signs. Looking at the second component it's clear that the sign relating 1 and 3 is $\left(\frac{p}{q}\right)$. Similarly, the sign relating 2 and 3 is $\left(\frac{q}{p}\right)$. So the sign relating 1 and 2 is $\left(\frac{p}{q}\right) \left(\frac{q}{p}\right)$. But to get from 1 to 2 we just changed the signs of $\frac{p-1}{2} \frac{q-1}{2}$ elements. QED

Correct the exponent of latter element of second product
Source Link
Loading
typeset Legendre symbol
Source Link
Douglas Zare
  • 28k
  • 6
  • 90
  • 130
Loading
cleaned up last bit of TeX
Source Link
Daniel Miller
  • 5.8k
  • 1
  • 42
  • 50
Loading
latex doesn't understand ()
Source Link
darij grinberg
  • 33.8k
  • 4
  • 118
  • 253
Loading
added 136 characters in body
Source Link
Noah Snyder
  • 28.1k
  • 4
  • 94
  • 170
Loading
fixed typos in formulas
Source Link
Noah Snyder
  • 28.1k
  • 4
  • 94
  • 170
Loading
added 59 characters in body
Source Link
Noah Snyder
  • 28.1k
  • 4
  • 94
  • 170
Loading
Source Link
Noah Snyder
  • 28.1k
  • 4
  • 94
  • 170
Loading