|
|
en.wikipedia.org/wiki/Zolotarev's_lemma
\[\left(\frac{a}{p}\right) = \varepsilon(\pi_a)\]左端是勒让德符号, 右端 $\varepsilon(\pi_a)$ 是置换 $π_a$ 的符号, $π_a$是$\bmod p$ 的非零剩余类在“乘以$a$”作用下的置换。
例如，取 $a = 2$ 和 $p = 7$。模 $7$ 的二次剩余为 $1$、$2$ 和 $4$，因此 $(2|7) = 1$ 和 $(6|7) = -1$。
$π_2$ 是$\bmod 7$ 缩系在 $×2$ 下的置换，可分解为 $(1,2,4)(3,6,5)$，因此$π_2$为偶置换，$\varepsilon(π_2)=1$。
$π_6$ 是$\bmod 7$ 缩系在 $×6$ 下的置换，可分解为 $(1,6)(2,5)(3,4)$，因此$π_6$为奇置换，$\varepsilon(π_6)=-1$。
证明
一般地，对于任何阶 $n$ 的有限群 $G$，很容易确定由 $G$ 的元素 $g$ 左乘得到的置换 $π_g$ 的符号。
置换 $π_g$ 是偶的，除非有奇数个长为偶数的轨道。 因此，假设 $n$ 为偶数， $k$ 是 $g$ 的阶，$π_g$ 是奇排列的条件， 是$n/k$为奇数(等价于，$g$ 生成的子群 $\left<g \right>$ 的 index 是奇数)。
我们将把它应用到模 $p$ 的缩系上，它是一个阶为 $p-1$ 的循环群。
模 $p$ 的本原根的 $j$ 次幂的 index 为 $i = \gcd(j, p-1)$.
一个非零数为$\bmod p$ 非二次剩余当且仅当它是原根的奇次幂。
因此，引理归结为，当 $j$ 为奇数时，$i$ 为奇数，这当然成立；当 $i$ 为奇数时，$j$ 为奇数，这是因为 $p-1$ 是偶数 （$p$ 是奇数）。 |
|
