Legendre 符号

1. 概述

于 初等数论 中, Legendre 符号 用 记录一个整数模奇素数是否为零、二次剩余 或二次非剩余. Fermat 小定理、Gauss 引理与二次互反律共同给出其计算规则.

2. 定义

定义 1 (Legendre 符号)

设 为 奇素数, . 依照 二次剩余 的分类定义：

称 为 关于 的 Legendre 符号.

3. 例子

例子 2 (模 的 Legendre 符号)

由模 的 二次剩余 为 可知：

这给出 Legendre 符号 的全部非零取值.

4. 相关性质

定理 3 (Euler 判别)

设 为 奇素数, . 则 Legendre 符号 满足：

证明 4 (Euler 判别)

若 , 结论直接成立. 以下设 . 每个模 的 二次剩余 都可写成 , 因而由 Fermat 小定理：

由 二次剩余的个数, 这已经给出多项式 在 有限域 中的 个根, 因而它们就是全部根. 若 是二次非剩余, 则 ; 又由 Fermat 小定理有 , 故 .
这两种情形恰与 Legendre 符号 的定义一致.

命题 5 (Legendre 符号的基本性质)

设 为 奇素数, . 则 Legendre 符号 满足：

1. 若 , 则 ;
2. .

证明 6 (Legendre 符号的基本性质)

1. 由 Legendre 符号 的定义, 两个整数属于同一个模 剩余类 时, 其是否为零或 二次剩余 完全相同.
2. 由 Euler 判别： 等式两侧都属于 , 而 为奇数, 故模 同余蕴含它们相等.
   

定理 7 (Gauss 引理)

设 为 奇素数, 且 . 对 , 取 的最小正模 余数, 并设其中大于 的共有 个. 则：

证明 8 (Gauss 引理)

将上述余数中大于 的项改取其相反数, 得到 个属于 的整数. 它们模 两两不同, 因而恰为该集合的一个 置换. 所以：

阶乘与 互素, 可由 同余式中的互素消去律 消去. 再使用 Euler 判别 即得所述 Legendre 符号.

定理 9 (二次互反律与补充律)

设 为不同的 奇素数. 则：

1. ;
2. ;
3. .

证明 10 (二次互反律与补充律)

1. 由 Gauss 引理 可将两个符号的指数奇偶性分别写为： 在矩形 、 中, 直线 不经过整点; 上述两和分别计数直线两侧的整点, 故其和为 . 代回 Gauss 引理即得第 1 条.
2. 第 2 条直接由 Euler 判别 得到.
3. 在 Gauss 引理 中取 . 大于 的最小正余数个数为 , 其奇偶性与 相同, 故得到第 3 条.
   

推论 11 ( 是二次剩余的判据)

设 为 奇素数. 则同余式 有解, 当且仅当 .

证明 12 ( 是二次剩余的判据)

由 Legendre 符号 的定义与 二次互反律与补充律 的第 2 条：

右侧等于 当且仅当 为偶数, 即 .

5. 相关概念

• 二次剩余
• Jacobi 符号
• Euler 函数
• 有限域

6. 术语翻译

中文	英文
Legendre 符号	Legendre symbol
Euler 判别	Euler’s criterion
Gauss 引理	Gauss’s lemma
二次互反律	law of quadratic reciprocity

初等数论