二次剩余

定义

对于正整数 \(m > 1\)\(m \nmid a\),如果存在 \(x^2 \equiv a \pmod m\),就称 \(a\) 是模 \(m\) 的二次剩余,否则就称 \(a\) 是模 \(m\) 的二次非剩余。

存在性判定

这一部分主要参考了 A Friendly Introduction to Number Theory。

先来考虑模奇素数 \(p\) 的情况。

\(g\)\(p\) 的一个原根,容易看出,\(a \equiv g^k \pmod p\) 是模 \(p\) 的二次剩余当且仅当 \(2 \mid k\),此时模 \(p\) 意义下存在两个 \(x\) 满足 \(x^2 \equiv a \pmod p\),设它们为 \(x_1,x_2\),则 \(p \mid x_1+x_2\)

这也同时指出,恰有 \(\frac {p-1} 2\) 个模 \(p\) 的二次剩余和 \(\frac{p-1} 2\) 个模 \(p\) 的二次非剩余。

由于 \(g^a \cdot g^b = g^{a+b}\),二次剩余与二次剩余的乘积是二次剩余,二次剩余与二次非剩余的乘积是二次非剩余,二次非剩余与二次非剩余的乘积是二次剩余。

这个性质可以用勒让德符号方便地描述,定义 \(a\)\(p\) 的勒让德符号为 (我们不讨论 \(p \mid a\) 的情况)

\[ \left({a\over p}\right)= \begin{cases} 1& \text{$a$ 是模 $p$ 的二次剩余}\\ -1& \text{$a$ 是模 $p$ 的二次非剩余} \end{cases}\]

则上面的性质可以表述为

\[ \left({ab\over p}\right) = \left({a\over p}\right) \left({b\over p}\right) \tag {1} \]

定理 1 (欧拉准则) \(\left({a\over p}\right) \equiv a^{\frac{p-1}2} \pmod p\)

证明\(a\) 是模 \(p\) 的二次剩余,设 \(a = g^{2k}\),则 \(a^{\frac{p-1}2} \equiv (g^{k})^{p-1} \equiv 1 \pmod p\)。所有 \(x > 0\) 都是 \(x^{p-1}-1 \equiv 0\) 的解,而 \(x^{p-1}-1 \equiv (x^{\frac{p-1}2}-1)(x^{\frac{p-1}2}+1)\)。由拉格朗日定理可知 \(x^{\frac{p-1}2}-1 \equiv 0 \pmod p\) 至多有 \(\frac{p-1}2\) 个根,而全部 \(\frac{p-1}2\) 个二次剩余都是这个方程的根。所以对于模 \(p\) 的二次非剩余 \(a\)\(a\)\(x^{\frac{p-1}2}+1 \equiv 0 \pmod p\) 的根,所以 \(a^{\frac{p-1}2} \equiv -1 \pmod p\)

似乎推广到 \(p^k\) 上,把 \(\frac{p-1}2\) 改成 \(\frac{\phi(p^k)}2\) 也可以类似地证明 (如果不对的话请告诉我一下)。

欧拉准则不是很方便描述问题,同时还必须分解素因数才能判定,但是用在求解算法中足够了,如果没有兴趣可以跳过下面一段内容。

二次互反律相关内容 (点击展开)

定理 2 (二次互反律)\(p,q\) 为奇素数,则 \(\left({p\over q}\right) \left({q\over p}\right) = (-1)^{\frac{p-1}2 \cdot \frac{q-1}2}\)

注意这里是乘而不是加。

有了这个定理之后,我们可以类似欧几里得算法地求解 \(\left({p\over q}\right)\),但是这个定理只在 \(p,q\) 是奇素数时成立,所以在翻转前我们要先把 \(p\) 分解素因数,再利用等式 \((1)\) 求解,同时我们还必须要能够直接求出 \(\left({2\over p}\right)\),因为它不能翻转。下面我们会一一解决这些问题。

我们先给出二次互反律的一个证明。

\(a,p\) 是奇素数。

\(\left( a\over p \right) \equiv a^{\frac{p-1}2} \pmod p\)

\(P = \frac{p-1}2\),考虑序列 \(a, 2a, \cdots, Pa\)

这个序列中的数的乘积为 \(a^P P!\),其中 \(a^P\) 是我们想求出的。

显然这个序列中任意两个数模 \(p\) 不同余。事实上,把这个序列中每个数改写为一个与其模 \(p\) 同余的 \([-P, P]\) 中的数,得到的序列任意两个数绝对值都不同。假设有两个数绝对值相同,那么存在 \(p \mid k_1 P + k_2 P, 1 \le k_1 < k_2 \le P\),显然 \((p, P) = 1\),所以 \(p \mid k_1+k_2\),这与 \(2 \le k_1+k_2 \le 2P \le p-1\) 矛盾。设这个序列中有 \(\mu(a,p)\) 个负数,则这个序列中的数乘积为 \(P! \mu(a,p)\)

于是我们就得到了 \(P! \mu(a,p) \equiv P!a^P \pmod P \Rightarrow a^P \equiv \mu(a, p) \pmod p\)

接下来只需证明 \(\mu(a, p) + \mu(p, a) = \frac{p-1}2 \cdot \frac{a-1}2\) 即可。

\(\mu(a,p)\)\(a, 2a, \cdots, Pa\) 中有多少个数 \(x\) 满足 \(x \bmod p > P\)问题的形式逐渐变得类欧几里得起来。

引理 1 \(\mu(a,p) \equiv \sum_{k=1}^P \lfloor \frac{ka}p \rfloor \pmod 2\)

证明\(ka = q_k p + r_k\),其中 \(-P \le r_k \le P\)。根据 \(\mu(a,p)\) 的定义,恰好有 \(\mu(a,p)\)\(r_k < 0\),则 \(\sum_{k=1}^P \lfloor \frac{ka}p \rfloor \equiv -\mu(a,p) + \sum_{k=1}^P q_k \pmod 2\)。只需证 \(2 \mid \sum_{k=1}^P q_k\)。由 \(p,a\) 是奇素数,\(ka = q_kp+r_k \Rightarrow k = q_k + r_k \pmod 2\)\(\sum_{k=1}^P k \equiv \sum_{k=1}^P q_k + r_k \pmod 2\),之前已经证明了 \(r_k\) 的绝对值两两不同,而在模 \(2\) 意义下正负是无所谓的,这就证明了 \(\sum_{k=1}^P q_k \equiv \sum_{k=1}^P r_k - \sum_{k=1}^P k\equiv 0 \pmod 2\)

于是这个问题变成了类欧几里得问题的形式。我们甚至可以直接用类欧几里得算法求解。

接下来应该就是 OI 选手很熟悉的操作了,设 \(p, q\) 是奇素数,\(P = \frac{p-1}2, Q = \frac{q-1}2\),不难证明

\[ \sum_{k=1}^P \lfloor \frac{kq}p \rfloor + \sum_{k=1}^Q \lfloor \frac{kp}q \rfloor = PQ \]

从而 \(\mu(a,p) + \mu(p,a) \equiv \frac{a-1}2 \cdot \frac{p-1} 2 \pmod 2\),这就完成了二次互反律的证明。

接下来我们要解决的问题是可能在分解时出现的 \(\left( 2\over p \right)\)。显然 \(\mu(2, p) = P - \lfloor \frac P 2 \rfloor\)

于是我们就得到了结论,若 \(p\) 是奇素数:

\[ \left({2\over p}\right)= \begin{cases} 1& \text{$p \equiv 1\ \text{或}\ 7 \pmod 8$}\\ -1& \text{$p \equiv 3\ \text{或}\ 5 \pmod 8$} \end{cases} \tag 2 \]

用这个就足以在很多情况下方便地手算了。但是在素因数分解往往很困难,所以如果有一个不依赖于 \(p,q\) 是素数的方法会更好,这就引出了雅可比符号。对于任意的整数 \(a\) 和正奇数 \(b\),把 \(b\) 写成素数的乘积 \(b = p_1 \cdots p_r\),定义

\[ \left(a \over b \right) = \prod_{k=1}^r \left(a \over p_k \right) \]

不难验证在雅可比符号中,等式 \((1),(2)\) 仍然成立。但是如果二次互反律要成立,必须限定 \(p,q\) 为正奇数 (这也很容易验证)。

这也就意味着如果上面是偶数,必须先分解出一个 \(2\) 再翻转。

如果上下很接近,有时候可以先分解一个 \(-1\) 来化简,但是注意翻转时上面必须是正数。

注意雅可比符号只是提供了一种计算 \(b\) 为奇素数时 \(\left(\frac a b\right)\) 的方式,\(b\) 不为奇素数时它并不能够反应 \(a\) 是否是模 \(b\) 的二次剩余。

求解

\(x^2 \equiv a \pmod p\) 的一组解。

目前不会素数幂。

一个特殊情况

\(p\) 是一个满足 \(p \equiv 3 \pmod 4\) 的素数时,如果 \(a\) 是模 \(p\) 的二次剩余,容易验证 \(x = a^{\frac{p+1}4}\) 是一组解。

Cipolla 算法

Cipolla 算法可以求解 \(p\) 为奇素数的情况。

先检验 \(a\) 是不是模 \(p\) 的二次剩余。

首先找到一个数 \(b\) 使得 \(b^2-a\) 是模 \(p\) 的二次非剩余,随机几次用欧拉准则检验一下即可。(感性理解应该期望 \(\mathcal O(1)\),但是因为 \(b^2\) 并不是所有数都能取到的所以感觉还是需要证明的,我不会)

\(\omega = \sqrt {b^2 - a}\),考虑所有形如 \(k + l\omega\ (0 \le k,l < p)\) 的数构成的集合。我们可以在这个集合上定义加法和乘法:

\[ (k_1 + l_1\omega) + (k_2 + l_2\omega) = ((k_1+k_2)\bmod p) + ((l_1+l_2) \bmod p)\omega \\\\ (k_1 + l_1\omega) \times (k_2 + l_2\omega) = ((k_1k_2 +l_1l_2(b^2-a))\bmod p) + ((k_1l_2+k_2l_1) \bmod p)\omega \]

可以证明这个这个集合上的加法和乘法构成一个域。

那么 \(x = (b + \omega)^{\frac{p+1}2}\) 即是一组满足条件的解。

证明

\[ ((b + \omega)^{\frac{p+1}2})^2 \equiv (b+\omega)^{p+1} \equiv (b+\omega)^p (b + \omega) \]

用二项式定理展开 \((b+\omega)^p\),中间的项系数都是 \(p\) 的倍数。所以

\[ (b+\omega)^p (b + \omega)\equiv (b^p+\omega^p)(b+\omega) \equiv (b + \omega)(b - \omega) \equiv b^2 - (b^2 - a) \equiv a \]

同时由拉格朗日定理可知 \(x^2 \equiv a\) 在新定义的这个域上也只有两个解。而由于已知存在两个形如 \(k + 0\omega\) 的解,我们得到的解必定是形如 \(k + 0\omega\) 的,也就是得到了原问题的一组解。