State/Zolotarevs lemma

From SlugmathWiki

Lemma
Proof
Metadata

Lemma: (Zolotarev's Lemma) Suppose that $p$ is an odd prime number. Suppose that $a$ is an integer, and $a$ is not a multiple of $p$. Let $\FF_p^\times$ denote the set of nonzero residues, mod $p$. Let $\mu_a \colon \FF_p^\times \rightarrow \FF_p^\times$ be the "multiplication by $\bar a$" permutation: $$\mu_a(\bar x) = \bar a \bar x.$$

Then, the sign of the permutation $\mu_a$ equals the Legendre symbol: $$sgn(\mu_a) = \left( {a \over p} \right).$$

Logical Connections

This statement logically relies on the following definitions and statements: Def/Prime number, Def/Residue, Def/Permutation, Def/Sign of a permutation, Def/Legendre symbol, Def/Cycle type, State/Multiplicative inverses exist mod p, Def/Partition, Def/Cyclic permutation

The following statements and definitions rely on the material of this page: State/Quadratic reciprocity

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

Suppose that $p$ is an odd prime number. Suppose that $a$ is an integer, and $a$ is not a multiple of $p$. Let $\FF_p^\times$ denote the set of nonzero residues, mod $p$. Let $\mu_a \colon \FF_p^\times \rightarrow \FF_p^\times$ be the "multiplication by $\bar a$" permutation:

$$\mu_a(\bar x) = \bar a \bar x.$$

Observe that $\mu_a$ is a permutation of the set $\FF_p^\times$ with $p-1$ elements. We analyze the cycle type of the permutation $\mu_a$ in what follows.

	Suppose that $\bar x \in \FF_p^\times$, and $e \in \NN$. $\mu_a^e(\bar x) = \bar x$.
	We find that $\bar a^e \bar x = \bar x$ if and only if $\bar a^e = 1$, since multiplicative inverses exist in $\FF_p^\times$.
	Therefore, the length of the cycle containing $\bar x$ under the permutation $\mu_a$ depends only on $\bar a$, and not upon $\bar x$ itself.

It follows that there exists a positive natural number $\ell$, such that the permutation $\mu_a$ decomposes as the product of disjoint cycles, each of length $\ell$. We may connect this number $\ell$ to the Legendre symbol as follows:

	Let $\ell$ be the length of a cycle in the permutation $\mu_a$.
	Since $\ell$ is the length of the cycle containing $\bar a$, we find that $\mu_a^\ell(\bar 1) = \bar a^\ell = 1$. Recall that the Legendre symbol is given by: $$\left( {a \over p} \right) = \bar a^{(p-1)/2}.$$ It follows that
	if $\ell$ divides $(p-1)/2$, then $\left( {a \over p} \right) = 1$.

The cycles partition $p-1$ into subsets with $\ell$ elements. Therefore, there exists a positive natural number $m$ such that $p-1 = \ell m$. Furthermore, the sign of a cyclic permutation of length $\ell$ is $(-1)^{\ell + 1}$. Therefore, the sign of $\mu_a$ can be computed as: $$sgn(\mu_a) = (-1)^{m(\ell + 1)}.$$ Now, there are two cases to consider:

$m$ even

First, suppose that $m$ is even. Then $\ell (m/2) = (p-1)/2$, and $m/2$ is an integer, so $\ell$ divides $(p-1)/2$. It follows that $\left( {a \over p} \right) = 1$. Moreover, $sgn(\mu_a) = (-1)^{m(\ell + 1)} = 1$, since $m$ is even. Hence we find that the Legendre symbol equals the sign of the permutation $\mu_a$ in this case.

$m$ odd

Suppose that $m$ is odd. Since $\ell m = p-1$, and $p-1$ is even, it follows that $\ell$ is even. It follows that $sgn(\mu_a) = (-1)^{m (\ell + 1)} = -1$, since $m$ and $\ell+1$ are both odd. On the other hand, we find that:

$$\bar a^{(p-1)/2} = \bar a^{(\ell / 2) (m)}.$$

	Let $\bar b = \bar a^{(\ell / 2)}$.
	Then $\bar b^2 = \bar a^\ell = 1$. Hence $\bar b = \pm \bar 1$. Moreover, by minimality of $\ell$, we find that $\bar b \neq 1$.
	Hence $\bar b = -1$.

Now, we find that: $$\bar a^{(p-1)/2} = \bar b^m = (-1)^m = -1,$$ since $m$ is odd. Hence, we find that the Legendre symbol equals the sign of the permutation $\mu_a$ in this case.