数论初步 by @shr_

· · 算法·理论

数论初步

:::align{right} By @shr_

Fixed by @FlowerAccepted :::

以下规定：\forall 为“对于所有”之意，\exist 为“存在”之意，\blacksquare 为“证明结束”之意。

若没有特殊说明，认为涉及到的数字均为 V 级别。

一、整除与质数

记 a|b 表示 \exist c\in \N,a\times c=b。

记 p 为质数，当且仅当 \forall a\in\{2,3\dots n-1\},a\nmid p。

问题1.1：如何判断给定整数 x 是否为质数。

做法1.1：

​枚举 i:2\to \lfloor\sqrt{x}\rfloor，若对于所有 i，均有 i\nmid x，则 x 为质数。

​单次复杂度 O(\lfloor\sqrt{x}\rfloor)。

问题1.2：如何找出给定整数 x 的所有因数。

做法1.2：

​枚举 i:1\to \lfloor\sqrt{x}\rfloor，对于一个 i，如果 i\mid p，则 i 和 \frac{x}{i} 都是 x 的因数。而且求出的所有因数即为 x 的所有因数。

​单次复杂度 O(\lfloor\sqrt{x}\rfloor)。

问题1.3：给定 n，如何求 1\sim n 中所有数的所有因数。

做法1.3：

​枚举 i:1\to n，再枚举 j:1\to\lfloor\frac{n}{i}\rfloor，将 i 加入 i\times j 的因数。

​总复杂度为 O(\sum_{i=1}^n\frac{n}{i})=O(n\log n)。

问题1.4：给定 n，如何求 1\sim n 中所有质数。

做法1.4.1：直接应用做法1.3，每个只有两个因数的位置即为质数。复杂度 O(n\log n)。

做法1.4.2（埃氏筛）：发现没必要用每个数筛一遍倍数，用质数筛即可。复杂度 O(n\log\log n)。

做法1.4.3（欧拉筛/线性筛）：

​钦定每个合数都被最小的质因数筛掉，记合数 c=minp_c\times a。

​我们发现在 p_1 处枚举 a 不好做，即要找到所有最小质因数大于等于 minp_c 的数不容易。

​我们反过来在 a 处枚举 minp_c，记 minp_a 为 a 的最小质因数，则我们记录 pri_i 表示第 i 小的质数，每次遍历 pri 数组直到找到 pri_j=minp_a，此时可以用 pri_j\mid a 表示。

​复杂度 O(n)。

二、最大公因数与二元一次不定方程

欧几里得算法：

​不妨设 x>y，则 \gcd(x,y)=\gcd(x-y,y)。

​在 OI 中，我们可以用 \gcd(x,y)=\gcd(y,x\%y) 来做，此时如果 y=0 则 x 即为 \gcd。这种做法其实不用不妨设 x>y，复杂度 O(\log V)。

在 C++ 中，可以直接调用库函数 __gcd(x,y) 来求解 \gcd。

记 a\perp b 为 a 与 b 互质，即 \gcd(a,b)=1。

二元一次不定方程：形如 ax+by=c 的方程，其中 a,b,c\in \N，x,y\in \Z。

裴蜀定理：若 a\perp b，则 ax+by=1 必定有解。

证明（扩展欧几里得算法/exGCD）：

  1. 当 b=0 时，x=1,y=0 是一组合法解。
  2. 当 b\not=0 时，归纳假设方程 bx+(a\bmod b)y=1 有解 x=x_0,y=y_0。

​观察到 a\bmod b=a-\lfloor\frac{a}{b}\rfloor b，代入展开简单推导即可得到 ay_0+b(x_0-\lfloor\frac{a}{b}\rfloor y_0)=1。

​也即方程 ax+by=1 有解 x=y_0,y=x_0-\lfloor\frac{a}{b}\rfloor y_0。\blacksquare

解的存在性：方程 ax+by=c 有解当且仅当 \gcd(a,b)\mid c。

证明：

​记 d=\gcd(a,b),a'=\frac{a}{d},b'=\frac{b}{d},c'=\frac{c}{d}。

​对于 \Rightarrow 情况：

​有 d\mid a 与 d\mid b，因此 d\mid ax+by，因此 d\mid c，即 \gcd(a,b)\mid c。

​对于 \Leftarrow 情况：

​观察到方程 ax+by=c 等价于 a'x+b'y=c'，因此只讨论后者即可。

​观察到此时 a'\perp b'，因此根据裴蜀定理，方程 a'x+b'y=1 有解设为 x=x_0,y=y_0。

​则上述方程两端乘 c'，得到 a'(c'x_0)+b'(c'y_0)=c'，故 x=c'x_0,y=c'y_0 即为原方程的一组解，因此存在。\blacksquare

问题2.1：如何求解方程 ax+by=c（保证有解）。

做法2.1：用扩展欧几里得算法求得方程 ax+by=\gcd(a,b) 一组解，再乘 \frac{c}{\gcd(a,b)} 即可。复杂度 O(\log V)。

解空间结构：通解为 X=\{(x_0+kb',y_0-ka')\mid k\in\Z\}，其中 (x_0,y_0) 是一组特解，a',b' 定义如下。

​记 d=\gcd(a,b),a'=\frac{a}{d},b'=\frac{b}{d},c'=\frac{c}{d}。

​故如果 ax+by=c 有一组特解 x=x_0,y=y_0，我们可以在上述方程上加一个 a(b')+b(-a')=0，得到 a(x_0+b')+b(y_0-a')=c，也即 x=x_0+b',y=y_0-a' 也是 ax+by=c 的一组解。

​则由上述分析，我们知道 X=\{(x_0+kb',y_0-ka')\mid k\in\Z\} 为 ax+by=c 解集的子集。

​可以证明不存在其他解：

​证明：

​假设存在解 (x_1,y_1)\notin X，则将等式 ax_0+by_0=c 与 ax_1+by_1=c 相减，得到 y_0-y_1=\frac{a'(x_1-x_0)}{b'}。

​由于 x_0,x_1,y_0,y_1\in\Z，所以 \frac{a'(x_1-x_0)}{b'} \in\Z，由于 a'\perp b'，所以 b'\mid (x_1-x_0)，即 \exist k,x1-x0=kb'，即 (x_1,y_1)\in X，矛盾。\blacksquare

三、模意义下的加减乘除与指数运算

规定 a\bmod b=a-\lfloor\frac{a}{b}\rfloor b。

规定 a\equiv b\mod p 当且仅当 a\bmod p=b\bmod p。

加法性质：

减法（负元）性质：

乘法性质：

根据上述性质，我们可以得到自然数中有关加减乘的运算规律均在模意义下成立，即：

下面我们来讨论模意义下的除法问题，也即模意义下是否存在逆元。

逆元：对于一个数 a，如果存在 b\in [0,p-1] 使得 ab\equiv 1\mod p，则称 b 为 a 的模 p 意义下的逆元，记为 a^{-1}=b。（下面会证明逆元唯一）

不难发现，ab\equiv 1\mod p 可以推出 ba\equiv 1\mod p，因此 a 也为 b 的逆元，即 b^{-1}=a。

逆元存在性：对于一个数 a，模 p 意义下的逆元存在当且仅当 a\perp p。

​观察到 ab\equiv 1\mod p 成立当且仅当关于 b 和 k 的方程 ab+pk=1 有解。

​所以逆元存在当且仅当 \gcd(a,b)\mid 1，即 a\perp p。

逆元唯一性：对于一个数 a，其逆元如果存在，则唯一。

​观察方程 ab+pk=1，其通解为 X=\{(b_0+lp,k_0-la)\mid l\in\Z\}，所以 b 有一个大小 p 的周期，不难证明区间 [0,p-1] 中必定存在恰好一个解（分情况反证即可）。

问题3.1：如何求解给定数 a 在模 p 意义下的逆元（保证逆元存在）。

做法3.1.1：使用扩展欧几里得算法求解方程 ab+pk=1，在通解中找到位于 [0,p-1] 中的解，记为答案。复杂度 O(\log V)。

做法3.1.2（费马小定理）：

​费马小定理：若 p 为质数，且 a\bmod p\not=0，则 a^{p-1}\equiv 1\mod p。

​证明：

​首先证明一个引理：\forall x,y\in [1,p-1],x\not=y\Leftrightarrow ax\not\equiv ay\mod p。

​证明：由于 p 为质数，故 a 存在逆元 a^{-1}，假设 ax\equiv ay\mod p，两边同时乘 a^{-1}，得到 x\equiv y\mod p，矛盾。\blacksquare

​根据上述引理，我们不难得出集合 [1,p-1] 和集合 \{ax\mid x\in[1,p-1]\} 相同。则我们可以得到：

\begin{align} \prod_{x\in[1,p-1]}x&\equiv\prod_{x\in\{ax\mid x\in[1,p-1]\}}x\mod p \\ \prod_{i=1}^{p-1}x&\equiv\prod_{i=1}^{p-1}ax\mod p \\ &\equiv a^{p-1}\prod_{i=1}^{p-1}x\mod p \end{align}

​则最后一个式子两边同时乘 \prod_{i=1}^{p-1}x 的逆元即可得到 a^{p-1}\equiv 1\mod p。\blacksquare

​所以，如果 p 为质数，有 a\times a^{p-2} \equiv 1\bmod p，即 a^{-1}=a^{p-2}\bmod p，用快速幂求解即可。单次复杂度 O(\log p)。

做法3.1.3（欧拉定理）：

​欧拉函数：定义函数 \varphi(x) 为欧拉函数，其含义是 [1,x-1] 中有多少个数与 x 互质。

​欧拉函数具有下列两个性质：

​1. 积性函数：若 a\perp b，则 \varphi(ab)=\varphi(a)\varphi(b)。

​2. 在 p^k 处的取值（p 为质数）：\varphi(p^k)=(p-1)p^{k-1}。

​证明：观察到 [1,p^k-1] 中只有 p 的倍数与 p^k 不互质，因此用总数量 p^k-1 减去 p 倍数个数 p^{k-1}-1 可以得到与 p^k 互质的数的数量即为 p^k-1-(p^{k-1}-1)，也即 (p-1)p^{k-1}。

​问题3.2：求给定数字 x 的欧拉函数 \varphi(x)。

​做法3.2：对 x 质因数分解得到 x=\prod_{i=1}^cp_i^{e_i}，则根据上述两条性质可以得到：

\begin{align} \varphi(x)&=\varphi(\prod_{i=1}^cp_i^{e_i}) \\ &=\prod_{i=1}^c\varphi(p_i^{e_i}) \\ &=\prod_{i=1}^c(p_i-1)p_i^{e_i-1} \end{align}

​则对 x 质因数分解后按照公式求值即可。单次复杂度 O(\sqrt{x})。

​欧拉定理：若 a\perp p，且 a\bmod p\not=0，则 a^{\varphi(p)}\equiv 1\mod p。

​证明思路和费马小定理基本一致，只不过将后者证明中的集合 [1,p-1] 换为了 \{x\mid x\perp p\}，所以将 a 从 \prod 中提出来的时候指数是集合 \{x\mid x\perp p\} 的大小，即 \varphi(p)。

​故有 a\times a^{\varphi(p)-1} \equiv 1\mod p，即 a^{-1}=a^{\varphi(p)-1}\bmod p，用快速幂求解即可，复杂度 O(\log\varphi(p))，一般视作 O(\log p)。

问题3.2：给定 n 个数 x_1\dots x_n，求解模 p 意义下的 x_1^{-1}\dots x_n^{-1}（保证逆元存在）。

做法3.2（线性求逆元）：

​整个过程分为四步：

  1. 求解 x 的前缀积 X_i=\prod_{i=1}^nx_i\bmod p，这个可以用递推式 X_i=X_{i-1}x_i\bmod p 求解。复杂度 O(n)。
  2. 求解 X_n 的逆元 X_n^{-1}，这一步需要用上面求单值逆元的方法。不难证明 X_n\perp p，因此逆元存在。复杂度 O(\log p)。
  3. 求解 X_i 的逆元 X_i^{-1}，可以用递推式 X_i^{-1}=X_{i+1}^{-1}x_{i+1}\bmod p 逆序求解。复杂度 O(n)。
  4. 求解 x_i 的逆元 x_i^{-1}，可以用表达式 x_i^{i-1}=X_i^{-1}X_{i-1}\bmod p 求解。复杂度 O(n)。

​整体复杂度为 O(n+\log p)，一般视作 O(n)。

至此，我们完全解决了模意义下的除法问题。下面来解决指数运算问题。

指数性质（底数处理）：

我们观察到可以处理底数，但指数的处理并不平凡。

指数性质（指数处理）：

​扩展欧拉定理：若 a\not\perp p，且 b\geq\varphi(p)，有 a^b\equiv a^{b\bmod \varphi(p)+\varphi(p)}\mod p。

由于 b 是和 \varphi(p) 同阶的，所以我们基本可以说解决了指数处理的问题。

四、线性同余方程与线性同余方程组

同余方程：形如 f(x)\equiv 0\mod p 的方程，其中 f 可以是任意函数。

在本课件中我们只研究 f 为线性函数的情况，即线性同余方程。

线性同余方程：形如 ax\equiv b\mod p 的方程。

一般形式：

​经过上一章的讨论，我们知道方程 ax\equiv b\mod p 等价于方程 ax+pk=b。

​此时，如果有解，则有 \gcd(a,p)\mid b，所以我们可以简化一下方程，即：

​记 d=\gcd(a,p),a'=\frac{a}{d},p'=\frac{p}{d},b'=\frac{b}{d}。则方程 ax+pk=b 可以变为方程 a'x+p'k=b'，其中 a'\perp p'。

​也即等价于方程 a'x\equiv b'\mod p'。那么 a' 有逆元 a'^{-1}，因此方程可以转化为 x\equiv a'^{-1}b'\mod p'。

​所以，所有方程均可转化为 x\equiv b\mod p 的形式，这个形式我们称其为线性同余方程的一般形式。

线性同余方程组：n 个线性同余方程 x\equiv b_i\mod p_i 组合在一起称为线性同余方程组。

关于线性同余方程组解的存在性与周期性，我们会在做法4.1.2里面详细讨论。

问题4.1 求解给定的线性同余方程组。

做法4.1（中国剩余定理/CRT）：本做法的条件是 p_1,p_2\dots p_n 两两互质。

​整个过程分为三步：

  1. 求 a_i=\prod_{j\not=i} p_j。
  2. 求 a_i 在模 p_i 意义下的逆元 a_i^{-1}，即 a_ia_i^{-1}\equiv 1\mod p_i。该逆元存在原因是 p_i 两两互质，所以 a_i 和 p_i 互质。
  3. 解即为 x\equiv \sum_{i=1}^n b_i\times a_i\times a_i^{-1}\mod \prod p_i。

​证明：

​我们发现如果 j\not=i，那么有 p_i\mid a_j，因此有 a_j\equiv 0\mod p_i，因此 b_j\times a_j\times a_j^{i-1}\equiv 0\bmod p_i。

​所以对于任何 i 有如下推导：

\begin{align} \sum_{j=1}^nb_j\times a_j\times a_j^{-1}&\equiv b_i\times a_i\times a_i^{-1}\mod p_i \\ &\equiv b_i\mod p_i \end{align}

​故这个解满足所有线性同余方程。\blacksquare

做法4.2（扩展中国剩余定理/exCRT）：

​观察两个线性同余方程 x\equiv b_1\mod p_1 和 x\equiv b_2\mod p_2。

​我们将其写成二元一次不定方程的形式：x+p_1k_1=b_1 和 x+p_2k_2=b_2。

​将两个方程相减，得到 p_1k_1+p_2(-k_2)=b_1-b_2，不妨设 b_1-b_2\geq 0。则这是一个新的二元一次不定方程。

​观察到如果新的这个方程无解，那么这两个线性同余方程组成的线性同余方程组就无解。

​如果有解，不妨设通解为 \{(x_0+lp_2',y_0-lp_1')\mid l\in\Z\}，其中 p_1'=\frac{p_2}{\gcd(p_1,p_2)},p_2'=\frac{p_2}{\gcd(p_1,p_2)}，则将 k_1 的通解带入 x+p_1k_1=b_1 中可以得到：x=b_1-p_1(x_0+lp_2')=b_1-p_1x_0-lp_1p_2'，故可以看出 x 在 [0,p_1p_2'-1=\text{lcm}(p_1,p_2)-1] 中有唯一解，不妨设为 x_0。所以这个解可以表示为 x\equiv x_0\bmod \text{lcm}(p_1,p_2)。

​因此，上述操作可以看作将两个线性同余方程合并为一个新的线性同余方程。

​exCRT正是通过这种方式不断合并直至线性同余方程组化为一个单独的线性同余方程。复杂度 O(n\log V)。

​上述操作同时说明了CRT方法中解的唯一性，因为 p_i 两两互质的情况不可能无解，且解必定以 \prod p_i 为周期。

线性同余方程组的一个应用是，存储一些比较大的数，此时可以用小模数下的值来进行若干操作，在最后再通过CRT或exCRT来复原这个是数。