概念

勒让德符号

勒让德符号 (a/p) 表示 a 是否为模 p 的平方，其乘积性把判断问题分解为素数因子。

阅读路径

参考可汗学院 Get ready 机制：先修概念 → 当前概念 → 进阶概念，✓ 表示已读。

勒让德符号初等数论

01定义

勒让德符号

\left(\frac{a}{p}\right)

以

1,0,-1

三值编码「

a

是否模

p

的平方」。欧拉判别法把它化为一次幂运算，乘积性把判定分解为素因子——二次剩余问题的通用货币。

平方映射二对一：剩余与非剩余各占一半

$\left(\frac{a}{p}\right)=1$ （二次剩余）、 $-1$ （非剩余）、 $0$ （ $p\mid a$ ）； $x^2\equiv a$ 有解 $\iff$ 符号为 1——判定问题被压缩为一个数。

$\left(\frac{a}{p}\right)\equiv a^{(p-1)/2}\pmod p$ ：快速幂 $O(\log p)$ 即可判定；平方映射 $a\mapsto a^2$ 二对一，故剩余恰占一半。

$\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$ ：符号是完全乘性函数，判定复合数分解为素因子之积——二次特征的开端。

\left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}}\pmod p,\quad\text{值域}\ \{1,0,-1\}

欧拉 1740 年代研究二次剩余规律；勒让德 1785 年引入符号并陈述互反律（未完全证明）；高斯 1796 年 19 岁给出首个严格证明。

素性检验的二次剩余版本（Solovay-Strassen）、Goldwasser-Micali 概率加密、二次筛法的平滑性检测、数域中素分裂的判据。

二次剩余：x² mod p 的像集金色点为 (x, x² mod p)；横轴金块表示二次剩余

p 奇素数11