勒让德定理满足模运算：从数学直觉到计算实践的系统梳理

勒让德定理（Legendre's Theorem）是初等数论中关于二次剩余判定的基石性成果，其本质是为了解决一个经典问题：对于给定的奇素数 $p$ 和整数 $a$，如何判断同余方程 $x^2 equiv a pmod{p}$ 是否有解？若有解，称 $a$ 为模 $p$ 的二次剩余（quadratic residue）；否则为二次非剩余（quadratic non-residue）。

然而，穷举法在 $p$ 较大时完全不可行（如 $p = 10^7+19$ 时需计算近五百万次模平方）。勒让德定理给出了一个简洁的判定准则：

而勒让德定理满足模运算的核心结论是：

注意：此结论虽常被称作“勒让德定理”，实为欧拉先发现、勒让德推广并命名的成果，数学史上称其为欧拉判别法更为准确。它将原本离散的二次剩余判定问题，转化为一个模幂运算问题，极大提升了判定效率——这正是勒让德定理满足模运算的真正价值所在。

但需特别强调：该判定仅在 $p$ 为奇素数且 $gcd(a,p)=1$ 时成立。一旦 $p$ 合数或 $a$ 与 $p$ 不互质，必须引入雅可比符号（Jacobi Symbol）等更广义工具。

勒让德符号 $left(frac{a}{p}right)$ 是连接抽象代数结构与具体模运算的桥梁。其取值仅依赖于 $a$ 在模 $p$ 下的剩余类，因此可视为从 $mathbb{F}_p^times$ 到 ${1,-1}$ 的一个群同态（即二次特征标）。

基本性质

• 乘法性： $left(frac{ab}{p}right) = left(frac{a}{p}right)left(frac{b}{p}right)$
• 周期性： 若 $a equiv b pmod{p}$，则 $left(frac{a}{p}right) = left(frac{b}{p}right)$
• 特殊值： $left(frac{1}{p}right) = 1$；$left(frac{-1}{p}right) = (-1)^{frac{p-1}{2}} = begin{cases} 1 & p equiv 1 pmod{4} \ -1 & p equiv 3 pmod{4} end{cases}$
• 二次互反律： 对奇素数 $p,q$，有 $left(frac{p}{q}right)left(frac{q}{p}right) = (-1)^{frac{p-1}{2} cdot frac{q-1}{2}}$

补充定律

为高效计算，常结合以下补充公式：

这些公式使得我们无需计算大指数模幂，即可快速判断符号值——这正是勒让德定理满足模运算在理论层面的优雅体现：将复杂运算转化为模 $4$ 或模 $8$ 的简单余数判断。

快速模幂法（Exponentiation by Squaring）

计算 $a^e pmod{m}$ 的标准算法，时间复杂度 $O(log e)$：

递归互反律法（Legendre Symbol via Quadratic Reciprocity）

避免大数模幂，直接计算符号值：

此算法避免了大数乘法，每次递归将 $a$ 减小至 $< a$，时间复杂度 $O(log a cdot log p)$，适合超大素数场景（如 $p > 2^{64}$）。

应用延伸：模平方根计算（Tonelli–Shanks 算法）

当 $left(frac{a}{p}right) = 1$ 时，如何求 $x$ 使得 $x^2 equiv a pmod{p}$？Tonelli–Shanks 算法是通用解法，其核心依赖于勒让德定理满足模运算的判定结果——若符号为 $-1$，则无需尝试求根。

必须满足的三个前提条件

常见计算陷阱