关于二次剩余——开根号的神奇操作

很久以前看《数论入门》这本书的时候就听说了二次剩余，后来看《数论概论》的时候认真学习了一番，这回终于学会了程序实现。 下面简单介绍二次剩余的相关定理、算法等。 ### 一些定义 什么叫二次剩余呢？我们经常在实数集上做“开方”运算，简单地说就是求解方程 $x^2=a$。那么我们能不能在模意义下开方呢？也就是，能否解方程 $x^2\equiv a\pmod{p}$？ 为了方便，我们只讨论 $p$ 是质数的情形；而 $p=2$ 的情形稍有特殊，而且也很平凡，因此我们不讨论 $p=2$。简而言之，本文中 $p$ 是奇质数。 我们来看一些平方表。下表中的数字依次是 $1,2,3,\cdots,p-1$ 的平方。 $x^2\equiv 1,1 \pmod{3}$ $x^2\equiv 1,-1,-1,1 \pmod{5}$ $x^2\equiv 1,-3,2,2,-3,1 \pmod{7}$ $x^2\equiv 1,4,-2,5,3,3,5,-2,4,1\pmod{11}$ $x^2\equiv 1,4,-4,3,-1,-3,-3,-1,3,-4,4,1\pmod{13}$ $x^2\equiv 1,4,-8,-1,8,2,-2,-4,-4,-2,2,8,-1,-8,4,1\pmod{17}$ $x^2\equiv 1,4,9,-3,6,-2,-8,7,5,5,7,-8,-2,6,-3,9,4,1\pmod{19}$ $x^2\equiv 1,4,9,-7,2,-10,3,-5,-11,8,6,6,8,-11,-5,3,-10,2,-7,9,4,1\pmod{23}$ $x^2\equiv 1,4,9,-13,-4,7,-9,6,-6,13,5,-1,-5,-7,-7,-5,-1,5,13,-6,6,-9,7,-4,-13,9,4,1\pmod{29}$ 观察这些表可以发现，平方表是回文的。这个很容易理解，因为 $x^2\equiv (p-x)^2\pmod{p}$。 并且，我们发现，这张表中，每个数恰出现两次。会出现至少两次的原因在上一段已经解释了，那么为什么是**恰**两次呢？也就是，为什么模 $p$ 的缩系（记为 $M_p$）恰好有两个数的平方相等呢？ 假设 $\{a,b\}\sube M_p$（这隐含了 $a,b$ 模 $p$ 不同余），并且 $a^2\equiv b^2$。移项并因式分解得到 $(a+b)(a-b)\equiv 0$。由于 $a,b$ 不同余，因此 $a+b\equiv 0$ 一定成立，这就说明，两个不同余的数模 $p$ 平方相同，当且仅当他们的和是 $p$ 的倍数。这样就解释了**恰**两次。 还有另一个角度可以解释。由多项式拉格朗日定理知，$x^2\equiv a$ 这个二次方程至多有两个解；而只要这个数在表中出现了，那么就会出现两次。 由平方表中每个数恰出现两次知，平方表中共有 $\cfrac{p-1}{2}$ 种不同的数。那么我们可以进行以下定义： 若 $\exists x\in M_p,x^2\equiv a$，则称 $a$ 是 $\bmod p$ 的**二次剩余**。在 $M_p$ 中但不是二次剩余的数称为 $\bmod{p}$ 的**二次非剩余**。 注意这个定义和“电解质”、“非电解质”的定义有一点点类似：电解质和非电解质只讨论化合物，$\mathrm{Cl}_2$ 不是电解质也不是非电解质；二次剩余和二次非剩余只讨论缩系，$0$ 不是二次剩余也不是二次非剩余。 勒让德提出了一个简单的符号（但是 $\LaTeX$ 打起来很麻烦）来表示一个数是不是 $\bmod{p}$ 的二次剩余。$\left(\cfrac{a}{p}\right)=1$ 表示 $a$ 是 $\bmod{p}$ 的二次剩余，$\left(\cfrac{a}{p}\right)=-1$ 表示 $a$ 是 $\bmod{p}$ 的二次非剩余，$\left(\cfrac{a}{p}\right)=0$ 表示 $a$ 既不是 $\bmod{p}$ 的二次剩余也不是二次非剩余（这说明 $a\equiv 0\pmod{p}$）。这被称为勒让德符号。 ### 二次剩余的判定：欧拉准则 如何判断一个数是不是二次剩余呢？最简单也最暴力的方法就是直接枚举 $M_p$ 中的数计算平方，这样还能同时计算出这个数的“平方根”。复杂度是 $\mathrm{O}(n)$ ，通常可以用于本地处理。 事实上，勒让德符号是可以“计算”的！对，就是计算。 回忆费马小定理：$\forall a\in M_p,a^{p-1}\equiv 1$。那 $a^{\frac{p-1}{2}}$ 是多少呢？ 设 $b\equiv a^{\frac{p-1}{2}}$，那么 $b^2\equiv 1$。根据上面的讨论，我们知道，$b$ 要么是 $1$，要么就是 $-1$。事实上，$b$ 就等于 $\left(\cfrac{a}{p}\right)$。 我们用一个简单的办法证明。因为 $p$ 是奇质数，因此 $p$ 存在原根，取其一个原根 $g$。设 $a\equiv g^c$，那么 $a$ 是二次剩余当且仅当 $c$ 是偶数。如果 $c$ 是偶数，那么设 $c=2k\ (k\in \mathbb{N})$，则 $b\equiv a^{\frac{p-1}{2}}\equiv g^{c\cdot \frac{p-1}{2}}\equiv g^{k(p-1)}\equiv\left(g^{p-1}\right)^k\equiv 1$。反之，如果 $c$ 是奇数，设 $c=2k+1\ (k\in \mathbb{N})$，则 $b\equiv a^{\frac{p-1}{2}}\equiv g^{c\cdot \frac{p-1}{2}}\equiv g^{k(p-1)+\frac{p-1}{2}}\equiv g^{\frac{p-1}{2}}$。考虑 $-1$ 在原根 $g$ 下的指标 $t$ ，因为 $(-1)^2\equiv 1$，因此 $2t\equiv 0\pmod{p-1}$，知 $t$ 是 $\cfrac{p-1}{2}$ 的倍数；但 $t$ 不能是 $0$（$1$ 的指标是 $0$），因此 $t=\cfrac{p-1}{2}$。于是 $c$ 是奇数时，$b\equiv g^{\frac{p-1}{2}}\equiv -1$。 由此，我们（基本）证明了 $\left(\cfrac{a}{p}\right)=a^{\frac{p-1}{2}}$，这被称为**欧拉准则**。（事实上还要对 $a\equiv 0$ 的情况稍加讨论） 在 OI 中，要计算勒让德符号的值，欧拉准则已经基本够用；下面要介绍的二次互反律，是另一种计算勒让德符号的值，当然在 OI 中可能没有太大的意义。 ### 二次剩余的判定：二次互反律 欧拉准则计算勒让德符号时需要乘方，这对手算十分不友好。“二次互反律”这种计算方法类似与辗转相除，更便于手算。 这个定理的证明比较繁琐，我不打算在这里证明，可以看[这篇回答](https://www.zhihu.com/question/59572768/answer/254653900)。 这个定理的结论是，对不同的奇质数 $p,q$，$\left(\cfrac{p}{q}\right)\left(\cfrac{q}{p}\right)=(-1)^{\frac{(p-1)}{2}\frac{(q-1)}{2}}$。也就是，当且仅当 $p,q$ 均为 $4k+3$ 型质数时，$\left(\cfrac{p}{q}\right)$ 和 $\left(\cfrac{q}{p}\right)$ 不同。 利用二次互反律和另外几个结论，我们可以用另外一种方法计算勒让德符号。 我们先叙述这几个额外的结论。 1. $\left(\cfrac{a}{p}\right)=\left(\cfrac{a\% p}{p}\right)$。非常简单，根据定义就可得。 2. $\left(\cfrac{a^2}{p}\right)=1$。根据定义可得。 3. $\left(\cfrac{ab}{p}\right)=\left(\cfrac{a}{p}\right)\left(\cfrac{b}{p}\right)$（完全积性）。根据欧拉准则得证。 4. $\left(\cfrac{2}{p}\right)=(-1)^{\frac{p^2-1}{8}}$，也即当且仅当 $p\equiv \pm 1\pmod{8}$ 时，$2$ 是 $\bmod{p}$ 的二次剩余。这个结论需要用高斯引理证明，这里不进行过多叙述。 利用这几个结论，我们就能够用类似辗转相除的方法求勒让德符号了。 用这种方法计算 $\left(\cfrac{a}{p}\right)$ 的步骤如下： 1. 将 $a$ 分解质因数，并把每个质因数的次数模 $2$。假设 $a$ 的指数为奇数的质因数有 $q_1,q_2,\cdots,q_k$ 这 $k$ 个，那么 $\left(\cfrac{a}{p}\right)=\left(\cfrac{q_1}{p}\right)\left(\cfrac{q_2}{p}\right)\cdots \left(\cfrac{q_k}{p}\right)$ ，分别递归计算。这一步的依据是第 2, 3 条结论。 2. 经过第一步后，只需计算一个**质数** $q$ 的 $\left(\cfrac{q}{p}\right)$ 的值。讨论 $q$。 1. 如果 $q=2$，那么根据第 4 条结论直接返回值。 2. 如果 $q=p$，返回 $0$。 3. 如果 $q>p$，那么将 $q$ 模 $p$，返回上面的第 $1$ 步（分解质因数等）。 4. 如果 $q<p$，那么用二次互反律调整成 $q>p$ 的情形。 举个例子，计算 $\left(\cfrac{360}{2333}\right)$。 $$ \begin{aligned} &\left(\cfrac{360}{2333}\right)\\ =&\left(\cfrac{2^3\times3^2\times 5}{2333}\right)\\ =&\left(\cfrac{2}{2333}\right)\times\left(\cfrac{5}{2333}\right)\\ =&-\left(\cfrac{5}{2333}\right)\\ =&-\left(\cfrac{2333}{5}\right)\\ =&-\left(\cfrac{3}{5}\right)\\ =&-\left(\cfrac{5}{3}\right)\\ =&-\left(\cfrac{2}{3}\right)\\ =&1 \end{aligned} $$ 第一步是分解质因数，第二步是根据第 2,3 条结论把一个勒让德符号拆开，第三步是根据第 4 条结论计算，第四步运用二次互反律，第五步利用第 1 条结论取模，第六步运用二次互反律，第七步利用第 1 条结论取模，最后一步根据第 4 条结论计算出答案。 这个过程最为棘手的是分解质因数，这个并不太高效，所以这个算法对 OI 来说价值不是那么大。 ### 二次剩余的计算：Cipolla 算法 前面一段都是“没用的”，现在来讲一点对 OI 有用的：如何计算 $x^2\equiv a\pmod{p}$ 的解？ 尽管 $a$ 是 $\bmod{p}$ 的二次剩余，但在计算上述 $x$ 的过程中，可能会用到一些 $M_p$ 以外的数；就像求解有三个实根的三次方程的过程中仍有可能出现虚数一样。 求解二次剩余的 Cipolla 算法就用到了这样的扩域思想，求解的过程中要用到所谓的“虚数”。 我们首先在 $[0,p)$ 中**随机**取一个整数 $b$，使得 $b^2-a$ 是 $\bmod{p}$ 的二次非剩余。这一步看上去非常奇怪，但这是为扩域做准备。这一步是否一定能做到呢？也就是，是否有可能无论取什么 $b$，都会让 $b^2-a$ 不是二次非剩余呢？ 因为 $a$ 是 $M_p$ 中的元素，我们可以设 $b^2=1-ka$（$k=(1-b^2)a^{-1}$ 一定存在）。把所有二次剩余的 $k$ 排起来，这些 $k$ 一共只有 $\cfrac{p-1}{2}$ 个，而 $k$ 的取值范围是 $[0,p)$，所以一定存在一个 $b^2$，使得它减 $a$ 得到的数是二次非剩余。至于这样的 $b^2$ 有多少个，就不是那么容易得到；但期望意义下，不用随机太多的次数就能得到一个合法的 $b$。 我们设 $\omega^2=b^2-a$，注意这里 $\omega^2$ 是 $M_p$ 的一个元素（是一个二次非剩余），而 $\omega$ 本身并不存在于 $M_p$ 中，是一个“虚数”。而接下来的算法中要用到的数，就表示成 $c+d\omega$ 的样子，这和 $a+b\mathrm{i}$，$2+\sqrt{3}$ 差不多，在运算时都要分别处理。很自然地，$(x+y\omega)(u+v\omega)=(xu+yv\omega^2)+(xv+yu)\omega$。 接下来，我们说明几个性质。 - $(x+y)^p\equiv x^p+y^p\pmod{p}$。用二项式定理展开，得到 $(x+y)^p=\sum_{i=0}^p\mathrm{C}_p^ix^i y^{p-i}$，而由卢卡斯定理（或者简单讨论一下）可知，只有 $i=0$ 或 $i=p$ 时 $\mathrm{C}_p^i$ 不是 $p$ 的倍数，因此这个性质得证。 - $\forall x\in \mathbb{Z},x^p\equiv x\pmod{p}$。这个是费马小定理的直接推论，并且适用于任何整数，包括 $0$。 - $\omega^p\equiv -\omega$。$\omega^{p}=(\omega^2)^{\frac{p-1}{2}}\omega\equiv -\omega$，最后一步是因为 $\omega^2$ 是 $\bmod{p}$ 的二次非剩余。 根据这几个性质，我们可以证明，$x=(b+\omega)^{\frac{p+1}{2}}$ 就是 $x^2\equiv a\pmod{p}$ 的解！ 为什么呢？我们来推导。 $$ \begin{aligned} &x^2\\ =&(b+\omega)^{p+1}\\ =&(b+\omega)^p(b+\omega)\\ \equiv &(b^p+\omega^p)(b+\omega)\\ \equiv&(b-\omega)(b+\omega)\\ =&b^2-\omega^2\\ =&b^2-b^2+a\\ =&a \end{aligned} $$ 其中第一步代入 $x$ 的定义，第二步拆开以出现 $p$ 次方，第三步运用性质 1，第四步运用 $b^p\equiv b$ 和 $\omega^p\equiv -\omega$，接下来就是简单的化简了。经过这样的推导，我们就证明了这个 $x$ 是 $x^2\equiv a$ 的一个解；另一个解自然就是 $-x$ 了。 且慢！万一 $x$ 里面含有 $\omega$ 项怎么办？我们尝试用反证法说明这不可能成立。 假设 $x=u+v\omega\ (v\neq 0)$，那么 $x^2=u^2+2uv\omega +v^2\omega^2=(u^2+v^2\omega^2)+2uv\omega$。由于 $x^2\equiv a$ 不带 $\omega$ 项，因此 $2uv\equiv 0$；由于 $v\neq 0$，知 $u\equiv 0$（注意 $p$ 是奇质数）。这样 $x^2=v^2\omega ^2$。两边同乘 $v$ 的逆元（因为 $v$ 非零，所以逆元存在），得到 $\omega^2=(xv^{-1})^2$，从而 $\omega^2$ 不是二次非剩余，矛盾。 因此，$x$ 中一定不含 $\omega$ 项；也就是说，这么解出来的 $x$ 就是我们想要求的。 这个算法的主要瓶颈在于求 $(b+\omega)^{\frac{p+1}{2}}$ 需要快速幂，因此时间复杂度 $\mathrm{O}(\log p)$，比较优秀。 关于这个算法的记忆，我建议可以记下 $x=(b+\omega)^{\frac{p+1}{2}}$，然后从结果 $x^2=b^2-\omega^2$ 推出 $\omega^2=b^2-a$。 二次剩余可以直接在计算中应用，比如假设 $x^2\equiv 5\pmod{p}$，那么可以用 $x$ 代替 $\sqrt{5}$，比如 $\cfrac{\sqrt{5}+1}{2}\equiv \cfrac{x+1}{2}$，这样最后的运算结果模 $p$ 还是正确的。 ### 二次非剩余？不怕 我们知道，$5$ 是 $\bmod{10^9+9}$ 的二次剩余，但是 $\bmod{10^9+7}$ 下的二次非剩余。如果想要在 $\bmod{10^9+7}$ 下运用斐波那契数列的通项公式 $F_n=\cfrac{1}{\sqrt{5}}\left(\left(\cfrac{1+\sqrt{5}}{2}\right)^n-\left(\cfrac{1-\sqrt{5}}{2}\right)^n\right)$ 进行计算，是不是就没有办法了呢？ 受到上面算法的启发，我们是不是可以像上面那样，令 $\omega^2=5$，用“虚数”的形式来表示 $\sqrt{5}$ 呢？答案当然是肯定的。程序实现和上面类似，可能要额外实现复数的加法和减法。 事实上，这个方法被成为“扩域”，在神鱼的[这篇题解](https://www.luogu.com.cn/blog/_post/128046)里有一些介绍。如果题目中只有一个二次非剩余，那这种方法无疑是比较好用的；如果题目中有好几个二次非剩余，那虚数的计算就会变得十分繁琐（做过毒瘤数学题的都懂）。 那么这篇关于二次剩余的总结就到此结束了，希望能有所收获。