Throughout the post I use \((q\mid p)\) to denote the legendre symbol bc I’m lazy. Throughout the post \(p,q\) are distinct odd primes.

I’ve seen quite a few proofs of QRLaw. According to wikipedia there are hundreds. I don’t know how credible that is, but here’s some ones I’ve seen:

  • Geometric proof due to Einstein:
    • \[(q\mid p) = (-1)^{\sum_{u=1}^{(p-1)/2}\left\lfloor 2qu/p \right\rfloor}.\]
    • \(\sum_{u=1}^{(p-1)/2}\left\lfloor 2qu/p \right\rfloor\) is counting the number of lattice points in a certain triangle. You can do some symmetry and stuff.
  • Gauss sums: you “guess” a square root in the algebraic closure in terms of a gauss sum.
    • you then analyze when this square root is actually contained in the right field not just the algebraic closure.
  • Zolotarev’s lemma: this post

This proof is rather neat. I like it because we get to use permutations, which are one of my favorite objects.

my source

First, recall an important combinatorial property of permutations: the signature of a permutation is the number of inversions – \(i,j\) with \(i<j, \pi_i > \pi_j\) – in it mod 2. Equivalently, it is the number of transpositions to make the permutation.

Example. A cycle of length \(k\) has signature \((-1)^{k-1}\).

Lemma. Let \(\pi_m\) be the map \(x\mapsto mx \mod p.\) Then \((m\mid p) = \mathop{\mathrm{sgn}}(\pi_m)\).

Proof. Recall that \(a^{(p-1)/2} = 1\) iff QR.

Notice that \(\pi_m\) consists of \((p-1)/\text{ord}_p(m)\) many cycles, all of length \(\text{ord}_p(m)\). So you can just compute the signature and check that it matches the legendre symbol.

Theorem. QR LAW:

\[ (p\mid q) = (q\mid p) \cdot (-1)^{\binom{p}{2}\binom{q}{2}}. \]

Proof.

Let \(\pi: \mathbb{Z}_{pq}\to \mathbb{Z}_p \times Z_q\) be the canonical isomorphism between these rings. Namely, \(aq+bp \mapsto (a,b)\). Let \(\alpha,\beta\) be permutations of \(\mathbb{Z}_p \times \mathbb{Z}_q\) defined as \[ \alpha(x,y) = qx+y,y \] \[ \beta(x,y) = x, x+py. \] Define a permutation \(\lambda\) on \(\mathbb{Z}_{pq}\) as \(\lambda(x+qy) = px+y\).

Observe that

\[ \pi \lambda \pi^{-1} \alpha = \beta. \]

by the lemma above \(\mathop{\mathrm{sgn}}(\alpha) = (q\mid p)\) and \(\mathop{\mathrm{sgn}}(\beta) = (p\mid q)\).

By counting inversions in \(\lambda\) we see that \(\mathop{\mathrm{sgn}}(\lambda) = (-1)^{\binom{p}{2}\binom{q}{2}}\).