State/Quadratic reciprocity

From SlugmathWiki

Theorem
Zolotarev's Proof
Metadata

Theorem: (Quadratic Reciprocity) Suppose that $p$ and $q$ are distinct odd prime numbers. Then, the two Legendre symbols $\left( \frac{p}{q} \right)$ and $\left( \frac{q}{p} \right)$ are related by the following formula: $$\left( {p \over q} \right) \left( {q \over p} \right) = (-1)^{ { {p-1} \over 2} { {q-1} \over 2} }.$$

A convenient way to rephrase this formula is the following:

If $p$ and $q$ are distinct odd prime numbers, then
- If $p \equiv 3$, mod $4$, AND $q \equiv 3$, mod $4$, then $\left( {p \over q} \right) = - \left( {q \over p} \right)$.
- Otherwise, the two Legendre symbols are equal: $\left( {p \over q} \right) = \left( {q \over p} \right)$.

Logical Connections

This statement logically relies on the following definitions and statements: Def/Prime number, Def/Legendre symbol, State/Chinese remainder theorem, Def/Permutation, Def/Sign of a permutation, Def/Cyclic permutation, Def/Fixed point, State/Zolotarevs lemma, State/Counting subsets of a given cardinality

The following statements and definitions rely on the material of this page:

To visualize the logical connections between this statements and other items of mathematical knowledge, you can visit the following cluster(s), and click the "Visualize" tab: Clust/Theory of quadratic residues

The following proof is based upon a proof by Zolotarev from 1872.

Suppose that $p$ and $q$ are distinct odd prime numbers.

Let $S$ be the set of natural numbers between $0$ and $pq-1$ (inclusive). Suppose that $0 \leq x \leq p-1$ and $0 \leq y \leq q-1$. We introduce three notations for elements of $S$, using such a pair $(x,y)$:

Black bracket notation: $[x,y]$ stands for the unique element $s \in S$ such that $s \equiv x$, mod $p$ and $s \equiv y$, mod $q$. Such an element exists and is unique, by the Chinese remainder theorem.
Blue bracket notation: $[x,y]$ stands for the number $qx + y$. Every element of $S$ has a unique blue-bracket notation, since if $0 \leq n \leq pq-1$, then division by $q$ with remainder yields a quotient between $0$ and $p-1$, and a remainder between $0$ and $q-1$.
Red bracket notation: $[x,y]$ stands for the number $x + py$. Every element of $S$ has a unique red-bracket notation, since if $0 \leq n \leq pq-1$, then division by $p$ with remainder yields a quotient between $0$ and $q-1$, and a remainder between $0$ and $p-1$.

Now, "color-changing" is a permutation of the set $S$:

Let $\alpha \colon S \rightarrow S$ be the permutation given by: $\alpha([x,y])$ = $[x,y]$.
Let $\beta \colon S \rightarrow S$ be the permutation given by $\beta([x,y])$ = $[x,y]$.
Let $\theta \colon S \rightarrow S$ be the permutation given by $\alpha$($[x,y]$) = $[x,y]$.

In particular, if one "changes color" from black to blue, then blue to red, it is the same as "changing color" directly from black to red. Hence, we find that: $$\theta \circ \alpha = \beta.$$

We now compute the signs of the permutations $\alpha$, $\beta$, and $\theta$:

$sgn(\alpha)$, $sgn(\beta)$

If $s \in \ZZ$, we write "$s \mbox{ mod } p$" and "$s \mbox{ mod } q$" for the remainders obtained when $s$ is divided by $p$ or $q$, respectively. Then, we can convert between bracket notations as follows:

$[x,y]$ = $[qx+y \mbox{ mod } p, y]$.
$[x,y]$ = $[x, x+py \mbox{ mod } q]$.

Therefore, we can describe the permutations $\alpha$ and $\beta$, purely within black bracket notation:

$\alpha([x,y]) = [qx+y \mbox{ mod } p, y]$.
$\beta([x,y]) = [x, x+py \mbox{ mod } q]$.

For all $0 \leq y \leq q-1$, define: $$X_y = \{ s \in S \mbox{ such that } \exists x, 0 \leq x \leq p-1 \wedge s=[x,y] \}.$$ Similarly, for all $0 \leq x \leq p-1$, define: $$Y_x = \{ s \in S \mbox{ such that } \exists y, 0 \leq y \leq q-1 \wedge s = [x,y] \}.$$ Then, $\alpha = \alpha_0 \circ \alpha_1 \circ \cdots \circ \alpha_{q-1}$, where for $0 \leq y \leq q-1$, $\alpha_y([x,y]) = [qx + y \mbox{ mod } p, y], \mbox{ for all } [x,y] \in X_y$. In other words, $\alpha$ separately permutes each of the subsets $X_y \subset S$.

Similarly, $\beta = \beta_0 \circ \beta_1 \circ \cdots \circ \beta_{q-1}$, where for $0 \leq x \leq p-1$, $\beta_x([x,y]) = [x, x + py \mbox{ mod } q], \mbox{ for all } [x,y] \in Y_x$. In other words, $\beta$ separately permutes each of the subsets $Y_x \subset S$.

Let $a_y^p$ denote the permutation of $\{ 0,, \ldots, p-1 \}$, given by: $$a_y^p(x) = x+y \mbox{ mod } p.$$ Let $\mu_q^p$ denote the permutation of $\{ 0,1, \ldots, p-1 \}$, given by: $$\mu_q^p(x) = qx \mbox{ mod } p.$$

Let $a_x^q$ denote the permutation of $\{ 0,1, \ldots, q-1 \}$, given by: $$a_x^q(y) = x+y \mbox{ mod } q.$$ Let $\mu_p^q$ denote the permutation of $\{ 0,1, \ldots, q-1 \}$, given by: $$\mu_p^q(y) = py \mbox{ mod } q.$$

Then, observe that:

$a_y^p(\mu_q^p(x)) = a_y^p(qx \mbox{ mod } p) = qx + y \mbox{ mod } p$,
$a_x^q(\mu_p^q(y)) = a_x^q(py \mbox{ mod } q) = py + x \mbox{ mod } q$.

Thus, we find that:

$\alpha_y([x,y]) = [a_y^p \circ \mu_q^p(x), y]$,
$\beta_x([x,y]) = [x, a_x^q \circ \mu_p^q(y)]$.

It follows that the sign of the permutations can be computed: $$sgn(\alpha_y) = sgn(a_y^p) sgn(\mu_q^p), \mbox{ and } sgn(\beta_x) = sgn(a_x^q) sgn(\mu_p^q).$$ We compute the signs of some of these permutations here:

$sgn(a_y^p)$, $sgn(a_x^q)$

We consider when $y \equiv 0$ and $y \not \equiv 0$, mod $p$, separately.

$y \equiv 0 \mbox{ mod } p$	If $y \equiv 0$, mod $p$, then $a_y^p(x) \equiv x+0 \equiv x$, mod $p$, and $a_y^p$ is the trivial permutation of $\{0,1,\ldots, p-1 \}$. Hence $sgn(a_y^p) =$.
$y \not \equiv 0 \mbox{ mod } p$.	If $y \not \equiv 0$, mod $p$, then $a_y^p(x) = x+y \mbox{ mod } p$. If $i \in \NN$, and $(a_y^p)^i(x) = x$, then we have $x + iy \equiv x$, mod $p$. It follows that $iy \equiv 0$, mod $p$, so $i$ is a multiple of $p$ (since $y \not \equiv 0$ mod $p$, and $p$ is prime). Thus, the order of the permutation $a_y^p$ equals $p$. Therefore, $a_y^p$ is a cyclic permutation of length $p$. Hence $sgn(a_y^p) = (-1)^{p+1} =$ (since $p$ is odd).
Thus $sgn(a_y^p) = 1$. The same argument implies that $sgn(a_x^q) = 1$.

$sgn(\mu_q^p)$, $sgn(\mu_p^q)$

Observe that $\mu_q^p$ fixes $0$. On the nonzero elements, $\mu_q^p$ is precisely the "multiplication by $q$" permutation, mod $p$. Switching $p$ and $q$ yields the corresponding statement about $\mu_p^q$. Since $p$ and $q$ are distinct, Zolotarev's lemma implies that:

$$sgn(\mu_q^p) = \left( {q \over p} \right), \mbox{ and } sgn(\mu_p^q) = \left( {p \over q} \right).$$

Hence, we find that:

$$sgn(\alpha_y) = sgn(a_y^p) sgn(\mu_q^p) = \left( {q \over p} \right), \mbox{ and } sgn(\beta_x) = sgn(a_x^q) sgn(\mu_p^q) = \left( {p \over q} \right).$$

Therefore, $$sgn(\alpha) = \prod_{y=0}^{q-1} sgn(\alpha_y) = \left( {q \over p} \right)^q = \left( {q \over p} \right) \mbox{ since } q \mbox{ is odd.}$$ $$sgn(\beta) = \prod_{x=0}^{p-1} sgn(\beta_x) = \left( {p \over q} \right)^p = \left( {p \over q} \right) \mbox{ since } p \mbox{ is odd.}$$

$sgn(\theta)$

The permutation $\theta$ can be written simply as:

$$\theta(qx+y) = x + py.$$ The sign of $\theta$ can be computed by counting its derangements.

Suppose that $x,x',y,y' \in \NN$, and $0 \leq x,x' \leq p-1$, and $0 \leq y,y' \leq q-1$. Then, we find that: $$qx + y < qx' + y' \mbox{ iff } (x < x' \mbox{ or } ( x = x' \mbox{ and } y < y' ) ).$$ Similarly, we find that: $$x + py > x' + py' \mbox{ iff } (y > y' \mbox{ or } ( y= y' \mbox{ and } x > x' ) ).$$ It follows that $\theta$ deranges an inequality $qx + y < qx' + y'$ if both of the above statements are true. Since $x < x'$ contradicts $x > x'$, and $y < y'$ contradicts $y > y'$, we find that derangements arise precisely when both of the following are true:

$x < x'$ and $y > y'$.

In other words, the derangements of the permutation $\theta$ are in bijection with quadruples of integers $(x,x', y, y')$ satisfying the following two conditions:

$0 \leq x < x' \leq p-1$ and $0 \leq y' < y \leq q-1$.

These two conditions are independent. The number of pairs $(x,x')$ such that $0 \leq x < x' \leq p-1$ is precisely the number of subsets of $\{ 0, \ldots, p-1 \}$ with two elements. The number of such subsets is "$p$ choose $2$", or $p(p-1)/2$. Similarly, the number of pairs $(y,y')$, such that $0 \leq y < y' \leq q-1$ is equal to $q(q-1)/2$.

Hence, the number of derangements of $\theta$ is equal to: $pq \left( { {p-1} \over 2} \right) \left( { {q-1} \over 2} \right)$. Since $p$ and $q$ are odd, the sign of $\theta$ can now be computed: $$sgn(\theta) = (-1)^{pq { {p-1} \over 2} \cdot { {q-1} \over 2} } = ((-1)^{pq})^{{ {p-1} \over 2} \cdot { {q-1} \over 2}} = (-1)^{{ {p-1} \over 2} \cdot { {q-1} \over 2}}.$$ Hence the sign of $\theta$ is $(-1)^{{ {p-1} \over 2} \cdot { {q-1} \over 2}}$.

We have now found that:

$$sgn(\theta) = (-1)^{{ {p-1} \over 2} \cdot { {q-1} \over 2}}, \mbox{ and } $$ $$sgn(\alpha) = \left( {q \over p} \right), sgn(\beta) = \left( {p \over q} \right)$$

Since $sgn(\theta) = sgn(\alpha) sgn(\beta)$, we now find the law of quadratic reciprocity:

$$\left( {p \over q} \right) \left( {q \over p} \right) = (-1)^{ { {p-1} \over 2} { {q-1} \over 2} }.$$

State/Quadratic reciprocity

From SlugmathWiki

Logical Connections

Views

Personal tools

Navigation

Mathematics

Pegagogy

Search

Toolbox