数论概论读书笔记 22.二次互反律

全栈程序员-站长 • 2026年3月19日下午9:44 • 未分类 • 阅读 1

二次互反律

对于一个给定的数 $a$ ，我们要确定哪些素数 $p$ 以 $a$ 为二次剩余。在前一章中解决了 $a=-1$ 和 $a=2$ 时的问题。

这个时候我们可以通过查看 $p\%m$ 的一些结果得出 $a$ 是否是 $QR$ 或 $NR$ ，且 $m$ 较小，为 $4$ 和 $8$

下面要解决的是其他 $a$ 值的勒让德符号 $(\frac{a}{p})$ 的计算问题。

例如，假设要计算 $(\frac{70}{p})$ ，由前面的二次剩余乘法法则知， $(\frac{70}{p})=(\frac{2}{p})(\frac{5}{p})(\frac{7}{p})$

怎么计算 $(\frac{5}{p})$ 和 $(\frac{7}{p})$ 呢？

概括来说，怎么计算 $(\frac{q}{p})$ 呢？其中 $q$ 也为素数。因为由乘法法则知，素数可以解决后，整数都可以解决。（这是素数的精美之处）

通过打表观察后（此处略去500字……）

可以得到对于一些 $p,q$ 有 $\left( \frac{q}{p} \right)=\left( \frac{p}{q} \right)$

但有些不是，但不是的竟然都是 $\left( \frac{q}{p} \right)=-\left( \frac{p}{q} \right)$

这其中有没有模式呢？

有的。

定理二次互反律 设 $p,q$ 是不同的奇素数，则

证明前两部分已经证明，最后的部分见下一节

高斯（ $1777\sim 1855$ ）19岁的时候，独立发现了二次互反律，且其一生中给出了7种不同的证明方法

19世纪，数学家们又提出了三次和四次互反律

再后来这些都包括在类域论中。

在20世纪60年代和70年代，大批数学家提出了对类域论推广的一些猜想。今天称之为朗兰兹( $Langlands$ )纲领。

二次互反律不仅很美，也很实用。

它使我们可以翻转勒让德符号 $\left(\frac{q}{p}\right)$ ，用 $\pm \left(\frac{p}{q}\right)$ 来替代它，然后可以模 $q$ 化简 $p$ ，并不断重复此过程。

这样会使 $p,q$ 急剧下降。

下面是计算的一个例子：

因此，55是模179的二次非剩余。

当然，也可以应用等式 $\left(\frac{p}{q}\right)=\left(\frac{p-q}{q}\right)$ 。

二次互反律的时间复杂度大约等于 $O(log\ p)$

所以，计算勒让德符号的困难之处不是二次互反律的使用，而是对数字的因式分解。这一块时间复杂度是 $O(\sqrt{n})$

但是！ 你可能会问，如果不分解，继续做下去呗，这样答案是否正确？

正确！ 也就是说对于 $\left(\frac{q}{p}\right)$ ，之前是 $p,q$ 为素数，现在是对任意的整数 $a$ 和正奇数 $b$ ，可以给勒让德符号 $\left(\frac{a}{b}\right)$ 指定一个值，反复使用广义二次互反定律来计算结果。这种广义勒让德符号常称作雅克比符号。