整数环以及丢番图方程

#clippings #algo/math/number-theory #algo/math

定义带余除法

对于给定的任意整数 $a, b$ 其中 $b > 0$ ，存在唯一的整数对 $q, r$ 使得 $a = b q + r$ 且 $r \in [0, b - 1]$ 。

证明用到良序原则（自然数的非空子集必然存在一个最小元素）。

先考虑存在性的证明。构造集合 $S = {a - b k | k \in Z, a - b k \geq 0}$ ，那么必然存在一个最小元 $r$ ，满足 $a - q b = r, a = q b + r$ 。接下来证明 $r < b$ ，这很显然，因为如果 $r \geq b$ 则存在 $r^{^{'}} = r - b \geq 0$ ，也在集合 $S$ 中，矛盾。接下来证明唯一性。由于 $r \geq 0$ ，所以只存在唯一的 $r$ 满足 $0 \leq r < b$ ，那么也就只有唯一 $q$ 。

定义整除

若 $a = b q$ 则称 $b$ 整除 $a$ ，记作 $b ∣ a$ 。称 $b$ 是 $a$ 的约数。整除具有传递性。

定义最大公约数

对于两个数，如果 $d ∣ a$ 且 $d ∣ b$ 则称其为公约数，其中最大的称为最大公约数记作 $g c d (a, b)$ 。

定义素数只有 $1$ 和其本身两个约数的数是素数，除了 $1$ 和其本身还有其他的约数的数是合数， $1$ 和 $0$ 既不是素数也不是合数。

定理唯一分解定理

任意正整数 $n = \prod_{i = 1}^{m} p_{i}^{c_{i}}$ ，其中 $p_{i}$ 是质数。

定理欧几里德算法

$g c d (a, b) = g c d (b, a m o d b)$ 。其中 $a m o d b$ 代表 $a$ 带余除法 $b$ 所得的余数 $r$ 。

证明之前先证一个引理， $g c d (a, b) = g c d (b, a - b)$ 。假设 $g c d (a, b) = d$ ，设 $a = u d, b = v d, g c d (u, v) = 1$ ，那么 $a - b = d (u - v)$ 。所以 $g c d (b, a - b) = d g c d (v, u - v) = d$ 。这里用反证法，如果 $g c d (v, u - v) = k > 1$ ，那么设 $v = k x, (u - v) = k y$ 则 $u = k (x + y)$ ，那么 $g c d (u, v)$ 至少是 $k$ 。这和 $g c d (u, v) = 1$ 矛盾。

有了这个引理之后，根据带余除法的定义，就可以证明该定理了。

定理扩展欧几里德算法

定理裴蜀定理方程 $a x + b y = g c d (a, b)$ 存在整数解 $x = s, y = t$ 。

纯数学证明可以构造集合并继续应用良序定理，这里给出扩展欧几里德算法的直接构造。

设 $g c d (a, b) = d$ ，欧几里得算法的最后一步会得到两个数 $d, 0$ ，然后令，就得到了一组解。假设当前我们要求一组解满足 $a x + b y = d$ ，且我们已经得到了一组解满足 $b s + (a m o d b) t = d$ 。拆开来得到 $a t + b (s - ⌊ \frac{a}{b} t) = d$ ，所以我们可以令而得到一组解。一直这么推下去就可以得到最后的答案，其实这是一个高斯消元的过程。

定义同余

如果整数 $a, b$ 和 $m$ 满足 $m ∣ (a - b)$ ，则称 $a, b$ 模 $m$ 同余。记作 $a \equiv b (m o d m)$ 。

命题如果 $a_{1} \equiv b_{1} (m o d m)$ 而且 $a_{2} \equiv b_{2} (m o d m)$ ，则 $a_{1} \pm a_{2} \equiv b 1 \pm b 2 (m o d m)$ 且 $a_{1} a_{2} \equiv b_{1} b_{2} (m o d m)$ 。

定理消去律

设 $a, b, c \in Z$ ， $m$ 是一个正整数。如果 $g c d (c, m) = 1$ ，且 $a c \equiv b c (m o d m)$ ，则 $a \equiv b (m o d m)$ 。

$m ∣ (a c - b c) = c (a - b)$ ，由于 $g c d (c, m) = 1$ 所以 $m ∣ a - b$ 。

定义乘法逆元

$a^{- 1}$ 满足 $a a^{- 1} \equiv 1 (m o d m)$ 。显然乘法逆元不一定存在。

求关于 $x$ 的同余方程 $a x \equiv 1 (m o d b)$ 的最小正整数解。

也就是 $a x + b y = 1$ 的最小正整数解，运用扩展欧几里德算法即可。

求 $1, 2 \hdots, n$ 模 $p$ 的逆元。

设 $p = k i + j, 0 \leq j < i$ 。

\begin{array}{r} k i + j \equiv 0 (m o d p) \\ < b r > (k i + j) i^{- 1} j^{- 1} \equiv 0 (m o d p) \\ < b r > k j^{- 1} + i^{- 1} \equiv 0 (m o d p) \\ < b r > i^{- 1} \equiv - k j^{- 1} (m o d p) \\ < b r > i^{- 1} \equiv (p - [p / i]) \times (p m o d i)^{- 1} (m o d p) \end{array}

定义等价类

显然，同余关系是一种等价关系。如果有一种等价关系定义在集合 $S$ 上，则该等价关系会把集合 $S$ 划分为不相交的子
集，这些子集我们称为等价类。

定义同余类

考虑整数集合 $Z$ ，设 $m$ 为正整数，则模 $m$ 的同余关系把 $Z$ 划分为 $m$ 个等价类。任意整数 $a$ 所落在的等价类记为 $[a]_{m}$ ，即所有模 $m$ 同余的整数形成的集合。

模 $m$ 同余类的集合记为 $Z / m Z$ ，该集合恰好有 $m$ 个元素，即： $Z / m Z = [0]_{m}, [1]_{m}, \dots, [m - 1]_{m}$ 。

定义最小剩余系

$Z / m Z$ 的所有最小非负代表元的集合 ${0, 1, 2, \dots, m - 1}$ 。

定理费马小定理

$a^{p - 1} \equiv 1 (m o d p)$ 。

引理 $a \times i m o d p, 1 \leq a < i$ 是 $1, 2, \dots, p - 1$ 的一个置换。

反证法，若存在 $a i \equiv a j (m o d p)$ ，则 $i \equiv j (m o d p)$ 矛盾。

下证费马小定理

\prod_{i = 1}^{p - 1} i \equiv \prod_{i = 1}^{p - 1} a i = a^{p - 1} \prod {(i = 1)}^{p - 1} i (m o d p)

所以显然有 $a^{p - 1} \equiv 1 (m o d p)$ 。

定义欧拉函数

记 $1, 2, \dots, n$ 中与 $n$ 互质的数的个数为 $φ (n)$ ，即为欧拉函数。

命题若 $p$ 是素数， $φ (p) = p - 1, φ (p^{c}) = p^{c - 1} (p - 1)$ 。

显然 $p$ 的剩余系里都与 $p$ 互质，那么每 $p$ 个数里会有 $p - 1$ 个互质，于是 $φ (p^{c}) = p^{c} \frac{p - 1}{p}$ 。

定理欧拉函数是积性函数，即 $g c d (a, b) = 1 \Rightarrow φ (a b) = φ (a) φ (b)$ 。

这其实可以用剩余系得思想来推，即证明 $Z / a Z \times Z / b Z$ 双射 $Z / a b Z$ 。当然还可以用容斥的角度，类似上面的证明。还有一个比较巧妙的用了狄利克雷卷积，这里就不过论述。

命题 $\sum_{d | n} φ (d) = n$

${1, 2, \dots, n} = \cup_{d ∣ n} {x \in [1, n] \cap Z ∥ g c d (x, n) = d}$ ，而后者刚好就是 $φ (\frac{n}{d})$ 。

欧拉函数的应用

定理欧拉定理

$a^{φ (m)} \equiv 1 (m o d m), g c d (a, m) = 1$ 。

定义简化剩余系

所有和 $m$ 互质的数构成的剩余类的集合。

证明欧拉定理等价于证明简化剩余系 $\times a$ 是简化剩余系的置换，其实和上面的反证法一模一样。

定理扩展欧拉定理

好复杂，但是可以根据欧拉定理记忆，先丢一个证明。

定理素数的整除性

设 $a, b \in Z$ ， $p$ 为素数。如果 $p ∣ a b$ ，则 $p ∣ a$ 或 $p ∣ b$ 。

推论， $n > 0, n ∣ a b, g c d (n, a) = 1 \Rightarrow n ∣ b$ 。

定理欧几里得定理

素数有无穷多。

使用反证法。设素数有穷， $p_{1}, p_{2}, \dots p_{n}$ ，构造 $N = 1 + \prod_{i = 1}^{n} p_{i}$ ，这个数显然不能被任意一个素数整除，那么也就不能被任意一个数整除，所以它也是一个素数。

定理狄利克雷定理

存在无穷多的素数满足 $p \equiv a (m o d m)$ ，其中 $g c d (a, m) = 1$ 。

定理素数定理

记 $π (x)$ 为素数个数，则 $\underset{x \to \infty}{l i m} \frac{π (x)}{x / l n x} = 1$

定理威尔逊定理

$p$ 是素数的充要条件是 $(p - 1)! \equiv - 1 (m o d p)$

$p = 1$ 时显然不行。

先证充分性，对于有 $a^{- 1} \neq b^{- 1}$ ，我们只需将与 $a^{- 1}$ 配对即可，充分性得证。

必要性显然，若 $p$ 为合数则取一个质因子即可。

定理 Lucas 定理

$p$ 是质数。

(\binom{n}{m}) m o d p = (\binom{n / p}{m / p}) \times (\binom{n m o d p}{m m o d p}) m o d p

定理库默尔定理

$p$ 在 $(\binom{n}{m})$ 中的位数等于 $n + m$ 在 $p$ 进制下进位的次数。

定理扩展 Lucas 定理

等价于求

(\binom{n}{m}) m o d p^{c}

考虑由于逆元不一定存在所有不能直接求逆元，把 $p$ 的倍数全部除掉，得到 $n! = p^{[n / p]} ([n / p])! \prod \dots$ ，后面的东西显然可以预处理。前面的部分递归做即可。

code

定义素性测试

素性测试问题，即如何判断一个大的奇整数 n 是否素数。

试除法

枚举 $2 \sim n - 1$ ，看看能不能整除 $n$ 。这是最暴力的方法，时间复杂度

对上述算法优化，约数是成对出现的所以枚举到 $\sqrt{n}$ 即可，时间复杂度 $O (\sqrt{n})$ 。

Miller-Rabin 素性测试

费马小定理的逆定理虽然不成立，但是可以勉强用来判断。而满足费马小定理的合数称作卡麦尔数。

定理二次探测定理

如果 $p$ 为质数，则 $x^{2} \equiv 1 m o d p$ 且 $x \in [1, p - 1]$ 的解为 $x = 1, p - 1$ 。

我们可以在费马小定理后以此判断 $a^{(p - 1) / 2}, a^{(p - 1) / 4}$ 是不是 $1 / - 1$ 。

已经证明若随机选择 $k$ 个底数则这样做出现伪素数的概率不大于 $\frac{1}{4^{k}}$ 。

code

定义原根

对于群 $Z_{n}^{*}$ 是循环群，则称其生成元是 $n$ 的原根。即满足阶是 $φ (n)$ 的元素 $g$ 。

满足 $n = 2, 4, p^{a}, 2 p^{a}$ 的群 $Z_{n}^{*}$ 都是循环群。

原根可以生成群内所有元素，原根有 $φ (φ (n))$ 个。

定理原根判定定理

$g$ 是原根，当且仅当 $\forall i, g^{\frac{φ (n)}{p_{i}}} \equiv / 1 (m o d φ (n)), φ (n) = \prod p_{i}^{c_{i}}$ 。

最小原根的数量级是 $n^{0.25}$ 的。

定理中国剩余定理

物不知数问题：

有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？
化解为线性方程组来表示即为：

{\begin{cases} x \equiv 2 (m o d 3) \\ x \equiv 3 (m o d 5) \\ x \equiv 2 (m o d 7) \end{cases}

对于这个方程组我们可以对于每个方程构造一个数使得其模其它模数为 0，模自己的模数为答案。

即对于上面的方程可以构造：

{\begin{cases} a_{1} = 35 \\ a_{2} = 63 \\ a_{3} = 30 \end{cases}

全部加起来即可得到一组特解 $x_{0} = 128$ 。然后得到通解 $x = x_{0} + M t, t \in Z$ 。 $M$ 是模数的最小公倍数。

可以得到最小正整数解： $x = 23$ 。

通过这个例子我们可以得到下面的结论：

如果模数两两互素，设 $M = Π_{i = 1}^{n} m_{i}, M_{i} = \frac{M}{m_{i}}$ 。根据古人的智慧我们可以构造出一个特解： $x_{0} = \sum_{i = 1}^{n} b_{i} M_{i} M_{i}^{- 1}$ 。

容易证明这个特解是对的，然后我们就可以得到通解： $x = x 0 + M$ 。

多数情况下模数不是质数，所以要用 exgcd 求逆元。

定理扩展中国剩余定理

这个时候，我们就要每个方程轮流按顺序求解。

假设我们已经求出一个解。这个解满足前个方程。现在我们将其和第个方程合并。

具体操作就是将其代入第个方程来解出得到未知数的一个通解。

设第个方程是形如的。

解方程的过程：

x_{0} + M t \equiv a (m o d b)

M t \equiv a - x_{0} (m o d b)

如果这个方程无解则整个方程组无解。

设 $g = g c d (M, b)$

解得： $t = t_{0} + \frac{b}{g} t^{^{'}}, t^{^{'}} \in Z$ 。

带回 $x$ 的解，得： $x = x_{0} + M (t_{0} + \frac{b}{g} t^{^{'}}) = x_{0} + M t_{0} + l c m (M, b) t^{^{'}}, t^{^{'}} \in Z$ 。

将 $x_{0}$ 更新为 $x_{0} + M t_{0}$ ， $M$ 更新为 $l c m (M, b)$ 即可。

第一个方程显然可以得到一组解

定义二次剩余

设 $p$ 是奇素数， $a$ 是与 $p$ 互质的整数，询问是否存在 $x$ 使得 $x^{2} \equiv a (m o d p)$ 。

定义勒让德符号

定义 $a m o d p$ 的勒让德符号为：

(\frac{a}{p}) = {\begin{cases} 1 (e x i s t) \\ - 1 (n o t) \\ 0 (p ∣ a) \end{cases}

定义欧拉准则

(\frac{a}{p}) \equiv a^{\frac{p - 1}{2}} (m o d p)

当 $(\frac{a}{p}) = 1$ 时， $\exists x, x^{2} \equiv a, (x^{2})^{(p - 1) / 2} \equiv 1 \Rightarrow a^{\frac{p - 1}{2}} \equiv 1$ 。

否则， $a^{(p - 1) / 2} - 1 \equiv / 0$ ，又 $0 \equiv a^{p - 1} - 1 = (a^{(p - 1) / 2} - 1) (a^{(p - 1) / 2} + 1) \Rightarrow a^{(p - 1) / 2} + 1 \equiv 0$ 。

推论

设 $p$ 是奇素数，则

(\frac{- 1}{p}) = {\begin{cases} - 1 & (p m o d 4 = - 1) \\ 1 & (p m o d 4 = 1) \end{cases}

定理二次互反律

(\frac{p}{q}) (\frac{q}{p}) = (- 1)^{\frac{(p - 1) (q - 1)}{4}}

定理 Cipolla 算法

我们随机一个 $n$ ，令 $ω = \sqrt{n^{2} - a}$ 。将数系扩充成 $F_{ω}$ ，相当于复数里面的 $i$ 。我们反复随机 $n$ ，直到 $n^{2} - a$ 不是一个二次剩余。然后大概可以证明这样的 $n$ 的大概有一半，所以期望随机二次既可以随机出一个，然后答案就是 $(n + ω)^{\frac{p + 1}{2}}$ 。

证明先考虑两个引理：

\begin{array}{r} ω^{p} = - ω \\ < b r > a^{p} + b^{p} \equiv (a + b)^{p} (m o d p) \end{array}

第一个考虑拆成 $(ω^{2})^{\frac{p - 1}{2}} \times ω$ ，第二个考虑二项式定理展开。

然后这个证明就很显然了，直接暴力平方展开然后替换，最后是一个平方差的形式，相信大家都会。

显然 $x, - x$ 都是二次剩余。

提交记录

定义离散对数

是一个整数 $x$ 对于给定的 $a, b, m$ 满足下面的方程：

a^{x} \equiv b (m o d m)

记作 $x = l o g_{a} b$ 。通常情况先我们把这叫做【阶】， $index$ 。记作 ${ind}_{a} b$ 。

显然离散对数不一定存在。比如： $2^{x} \equiv 3 (m o d 7)$ 。

定理 BSGS

当 $(a, m) = 1$ 时我们可以使用大步小步（Baby Step Giant Step）算法。

注意到 $(a, m) = 1$ ，我们有欧拉定理 $a^{φ (m)} \equiv 1$ 。所以 $a^{k}$ 至多有 $φ (m)$ 种取值（也就是其循环节为 $φ (m)$ ）。设 $x = k B - r, 0 \leq r \leq B - 1$ ， $B$ 是我们随便取的一个数，那么有 $a^{k B} \equiv b a^{r}$ ，我们预处理 $a^{0}, a^{1} \dots a^{B - 1}$ ，枚举 $k$ 即可求出 $x$ （其实这个过程已经可以求出阶了）。

时间复杂度 $O (B + \frac{φ (m)}{B})$ ，随便根号平衡一下得 $O (\sqrt{φ (m)})$ 。

定理扩展 BSGS

用于解决 $(a, m) \neq 1$ 时的情况。设 $d = g c d (a, m)$ ，那么有 $\frac{a}{d} a^{x - 1} \equiv \frac{b}{d} (m o d \frac{m}{d})$ 。于是这么一路递归除下去即可。注意判断无解，当 $d$ 不整除 $b$ 时即无解。

递归完之后就可以正常的 bsgs 了。

定理 pohlig-hellman 算法

这里我们不妨设模数是个大质数 $P$ 。我们可以找出一个原根 $g$ ，然后求 $g^{x} \equiv h (m o d P)$ 。

算法思想大概就是想把 $p - 1$ 质因数分解为 $\prod p_{i}^{e_{i}}$ ，然后计算 $x \equiv x_{i} (m o d p_{i}^{e_{i}})$ 。

考虑 $g^{p - 1} \equiv 1 (m o d P)$ 。所以有

(g^{x})^{\frac{p - 1}{p_{i}^{e_{i}}}} = (g^{x_{i} + k p_{i}^{e_{i}}})^{\frac{p - 1}{p_{i}^{e_{i}}}} \equiv (g^{\frac{p - 1}{p_{i}^{e_{i}}}})^{x_{i}} \equiv h^{\frac{p - 1}{p_{i}^{e_{i}}}} (m o d P)

所以令 $g^{\frac{p - 1}{p_{i}^{e_{i}}}}, h^{\frac{p - 1}{p_{i}^{e_{i}}}}$ 取代原来的 $g, h$ 就可以在 $p_{i}^{e_{i}}$ 范围内求 $x_{i}$ 了。

所以我们需要解决的问题变成了 $g^{x} \equiv h (m o d P)$ ，其中 $x \in [0, p_{i}^{e_{i}} - 1]$ 。考虑将 $x$ 写成 $p_{i}$ 进制数，显然有 $e_{i}$ 位，从低到高逐位确定。即 $x = x_{0} + x_{1} p_{i} + x_{2} p_{i}^{2} + \hdots + x_{e - 1} p_{i}^{e_{i} - 1}$ 。然后当我们想要求 $x_{j}$ 的时候，就计算 $(g^{x})^{\frac{p - 1}{p_{i}^{j + 1}}}$ ，容易发现这又可以写成 $g^{x_{j}} \equiv h (m o d P)$ 的形式，但是这时 $x_{j}$ 的范围就变成了 $[0, p_{i} - 1]$ 。这个时候我们就可以直接 BSGS 了。

综上所述，整个算法的复杂度为 $O (\sum e_{i} (l o g P + \sqrt{p_{i}}))$ 。比普通 BSGS 有了不小的提升。

定理 pollard-rho 算法

定义线性递推数列

主要研究二阶常系数齐次线性递推，即斐波那契数列。下面的公式仅考虑一般情况（ $n \geq 2$ ）

\begin{array}{r} f_{n} = f_{n - 1} + f_{n - 2} \\ f_{n - 1} f^{n + 1} - f n^{2} = (- 1)^{n} \\ f_{n + k} = f_{k} f_{n + 1} + f_{k - 1} f_{n} \\ f_{a} ∣ f_{b} \Leftrightarrow a ∣ b \\ g c d (f_{a}, f_{b}) = f_{g c d (a, b)} \end{array}

定理皮萨诺周期

斐波那契数列模 $m$ 的周期不超过 $6 m$ 。

WC 2021 斐波那契

这种分析的方法太经典了。

设 $f_{0} = 0, f_{1} =, f_{n} = f_{n - 2} + f_{n - 1}$ ， $f_{n}$ 就是常见的斐波那契数列，易得 $F_{n} = a f_{n - 1} + b f n$ 。

于是我们只需找出最小的 $n$ 使得 $a^{^{'}} f_{n - 1} = b^{^{'}} f_{n} (m o d m)$ ，如果 $m$ 是质数我们可以直接预处理（这里用到结论 $f$ 的循环节是 $O (m)$ 的）。

否则考虑除掉 $g c d (a^{^{'}}, b^{^{'}}, m)$ ，变成 $a_{1} f_{n - 1} = b_{1} f_{n} (m o d m_{1})$ ，注意到这时还是有可能不互质。

但是相邻斐波那契数是互质的，记 $p = g c d (a_{1}, m_{1}) = g c d (f_{n}, m_{1}), q = g c d (b_{1}, m_{1}) = g c d (f_{n - 1}, m_{1})$ ，可以再除掉这个 $p, q$ 。于是有 $a_{2} f_{n - 1} = b_{2} f_{n} (m o d m_{2})$ ，这时直接预处理 $\frac{f_{n}}{f_{n - 1}} m o d m_{2}$ 即可。

用一个三元组维护 $(p, q, \frac{f_{n}}{f_{n - 1}})$ 维护即可。

本文使用 Zhihu On VSCode 创作并发布