简谈数论

Fish_Chen · 2025-07-14 17:21:12 · 算法·理论

数论篇

一、基本工作：了解数论

• 数论是什么

数论是一种数学分支，英文 number theory，主要研究整数的性质。

二、整数除法

• 数学表达

在数论中，整数除法的结果通常为：商和余数。用数学公式表达即为 a=bq+r\ (0\le r < b ) ，其中 q 为商， r 为余数。

• 取余运算与取模运算

取余运算同样是在做除法时求得的余数，不过它允许结果的符号与被除数相同。

取模运算的结果是在进行完整数除法后得到的余数。因计算机中数据绝大多数时候进行的是取模运算，所以我们后面一律用“取模运算”来表述。

我们通常把取模运算记作 a \bmod b = r

三、一些基本的公式

• 基础公式

  设 a\bmod b = r 则有：\ 取商： q = \lfloor \frac{a}{b} \rfloor \ 被除数逆运算（商乘除数加余数）： a=\lfloor \frac{a}{b} \rfloor b + (a\bmod b)

特别地，在MO（数学奥赛）中有高斯取整函数： [x]

• 整除的一些性质

  如果 a 能够整除 b ，即 a\mod b=0 ，我们将其记作 b|a 。其中称 a 是 b 的倍数， b 是 a 的因数（约数）。

由此基础，我们可以发现：

1. b|a $ 等价于存在整数 $ k $ 使得 $a=kb
2. 若 a|b,c|d ，则 ac|bd
3. 自反性： a|a
4. 反对称性：若 a|b,b|a ，则 a=b
5. 传递性：若 a|b,b|c ，则 a|c
6. 线性法：若 a|b,a|c ，则 a|(mb+nc)
7. 消去律：若 ma|mb ，则 a|b

特别地， 1 是所有整数的约数， 0 是所有整数的倍数。

四、最大公因数和最小公倍数

• 定义

  最大公因数：亦称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个。 a,b 的最大公约数记为 (a,b) 。

最小公倍数：两个或多个整数公有的倍数叫做它们的公倍数，其中除 0 以外最小的一个公倍数就叫做这几个整数的最小公倍。整数 a,b 的最小公倍数记为 [a,b]

我们为了方便进行使用，在计算中使用 \gcd(a,b) 代表 a,b 的最大公因数；同时，以 lcm(a,b) 代表 a,b 的最小公倍数。

特别地， \gcd(a,b)\times lcm(a,b)=a\times b

五、一些定理和公式

• 求最大公因数

  1. 辗转相减法：当 a\ge b 时， \gcd(a,b)=\gcd(b,a-b)
  2. 辗转相除法：当 \gcd(a,b)=\gcd(b,a\mod b)
  3. 更相减损术（求高精度 a,b 的最大公因数）：

     分三种情况：

     一、若 a,b 均为偶数，则 \gcd(a,b)=2\gcd(\frac{a}{2},\frac{b}{2})

     二、若 a,b 一个是奇数，一个是偶数（假使 a 为奇数），则 \gcd(a,b)=\gcd(\frac{a}{2},b)

     三、若 a,b 均为奇数，则 \gcd(a,b)=\gcd(b,a-b)

• 算数基本定理（唯一分解定理）

  任何一个正整数 n 都可以唯一表示如下形式：

  n=\prod\limits_{i=1}^{+\infty} p_i^{e_i}

  其中 p_i 是第 i 个素数， e^i 是非负整数。

• 调和级数

  调和级数 H_n 被定义为正整数的倒数和，即：

  H_n=1+\frac{1}{2}+\frac{1}{3}+\dots+\frac{1}{n}=\sum\limits_{i=1}^{n}\frac{1}{i}

• 巴塞尔问题

  求正整数的倒数平方和，即：

  \sum\limits_{i=1}^{+\infty}\frac{1}{i^2}

  结果是 \frac{\pi^2}{6}

• 埃拉托斯特尼筛法（埃氏筛法）

  要得到自然数 n 以内的全部素数，必须把不大于 \sqrt n 的所有素数的倍数剔除，剩下的就是素数

• 欧拉筛法（线性筛）

  让每个合数只被其最小因子标记为非素数。\ 具体地，对 i=2,3,5,\dots,n 从小到大枚举目前筛出来的所有素数 p_j ，将 i\times p_j 标记为合数，当 i\mod p_j=v 时， i 中已经有了 p_j 这个因子，而之后的 p_{j+1},p_{j+2} 都大于 p_j ，所以这个时候退出循环。

• 模运算

  a+b\equiv(a\bmod p)+(b\bmod p) \pmod p a-b\equiv(a\bmod p)-(b\bmod p) \pmod p a\times b\equiv(a\bmod p)\times(b\bmod p) \pmod p

• 光速幂

  当底数 a 和模数 p 都确定时，令 B=\lceil \sqrt p\rceil ，则有：

  a^b\equiv(a^B)^{\lfloor\frac{b}{B}\rfloor}\times a^{b\mod B}\pmod p

  可以做到 O(\sqrt n) 预处理， O(1) 查询 a^b\mod p

• 乘法逆元

  乘法逆元的存在是为了在模意义下进行除法运算。\ 具体而言，对于模数 p ，我们希望对 a 找到一个数 x ，满足：

  a\times x\equiv 1 \pmod p

  此时 x 是 a 在模 p 意义下的乘法逆元，记为 a^{-1}=x 但是这个数不一定存在，如 a=0 的时候就一定不存在。而在模数 p 是素数的情况下，对于 a = 1,2,\dots,p-1 ，对应的乘法逆元 a^{-1} 都是存在的。

• 费马小定理

  对于素数 p 和 a=1,2,\dots,p-1 ，有：

  a^{p-1}\equiv 1\pmod p

  换言之：

  a\times a^{p-2}\equiv 1\pmod p

  即 a^{p-2}\mod p 是 a 的乘法逆元。

• 线性递推

  对于素数 p 和 i=2,3\dots,p-1 ，有：

  i^{-1}\equiv -\lfloor\frac{p}{i}\rfloor(p\mod i)^{-1}\pmod p

• 离线逆元

  给大素数 p 和 n 个数 a_1,a_2,\dots,a_n ，记 A=\prod\limits_{i=1}^{n}a_i ，求出 A^{-1}\mod p ，之后就有：

  a_i^{-1}\equiv A^{-1} \left( \prod\limits_{j=1}^{i-1} a_j\right)\left(\prod\limits_{j=i+1}^{n}a_j\right)\pmod p

  后面两个括号内的内容可以前后缀积处理。

• 整除分块

  对于一个整数 n ，它除以 1\sim n 之间的数后的商，只有不超过 2\sqrt n 种，且每种商对应的除数是一段连续区间。

对于除数 x\le\sqrt n ，对应的 \lfloor\frac{n}{x}\rfloor 最多有 \sqrt n 个。

对于除数 x > \sqrt n ，则有

不超过 \sqrt n 种。

同时 \lfloor\frac{n}{x}\rfloor 的值是非严格单调的，所以相同的 \lfloor\frac{n}{x}\rfloor 对应的除数 x 是连续的。

如果我们知道了 \lfloor\frac{n}{x}\rfloor=y 的除数 x 区间左端点 l ，则可以直接计算出右端点 r ：

通过一个简单的循环，可以在 O(\sqrt n) 的时间复杂度内得到所有的的 \lfloor\frac{n}{x}\rfloor 值和对应的区间，即整除分块。

• 线性丢番图方程

  目的：寻找整系数方程（组）的整数解\ 线性丢番图方程的标准形式为 ax + by = c ，其中 a, b, c 为整数， x, y 为未知数。

• 裴蜀定理

  裴蜀定理指出，对于线性丢番图方程 ax + by = c ，存在解的充要条件为 \gcd(a, b) | c\ 在模 g = \gcd(a, b) 意义下看方程：

  ax + by \equiv c \pmod g 0 \times x + 0 \times y \equiv c \pmod g c \equiv 0 \pmod g

  必要性得证。\ 充分性则由扩展欧几里得算法构造解给出。

• 扩展欧几里得算法

  构造线性丢番图方程 ax + by = \gcd(a, b) 的整数解。\ 不妨考虑辗转相除法的递归或迭代过程：

  ax + by=ay'+b\left(x'-\lfloor\frac{a}{b}\rfloor y'\right)

  系数对齐可以得到递归或迭代公式：

  \left\{ \begin{array}{c} x=y' \\ y=x'-\lfloor\frac{a}{b}\rfloor y' \end{array} \right.

  而对于递归的边界 a = \gcd(a, b), b = 0 ，方程退化为：

  \gcd(a, b)x = \gcd(a, b)

  由此可得解 x = 1, y = 0

要求线性丢番图方程 ax + by = c 的特解，把 ax + by = \gcd(a, b) 的 特解乘上 \frac{c}{\gcd(a,b)}

• 中国剩余定理（CRT）

  我们想要求解如下的线性同余方程组：

  \left\{ \begin{array}{c} x\equiv a_1\pmod {m_1} \\ x\equiv a_2\pmod {m_2}\\ \vdots \\x\equiv a_n\pmod {m_n} \end{array} \right.

  中国剩余定理指出，在 m_1,m_2,\dots,m_n 两两互素的情况下的解：

  x=kM+\sum\limits_{i=1}^{n}a_iM_it_i M=\prod\limits_{i=1}^{n}m_i,M_i=\frac{M}{m_i} t_i=M_i^{-1}\bmod m_i

  扩展：假设有一个解 x_0 ，则其通解为：

  x\equiv x_0+klcm(m_1,m_2)

  实际上就是合并成为新的线性同余方程：

  x\equiv x_0\pmod {lcm(m_1,m_2)}

• 欧拉函数

  欧拉函数 \phi(n) 定义为 1 \sim n 中与 n 互素的数的个数，即：

  \phi(n)=\sum\limits_{i=1}^{n}[\gcd(n,i)=1]

  简化式子可得：

  \phi(n)=n\prod\limits_{i=1}^{k}\left(1-\frac{1}{p_i}\right)

• 积性函数

  数论函数是指定义域为正整数的函数。\ 积性函数是指在 m, n 互素的情况下满足 f(nm) = f(n)f(m) 的数论 函数。\ 从单个欧拉函数的计算式可以看出，欧拉函数 \phi(n) 是一个典型的积性函数。\ 此外典型的积性函数还有莫比乌斯函数 \mu(n) 、约数个数函数 \tau(n) 、 约束和函数 \sigma(n) 等。\ 从定义式可以看出，积性函数 f(n) 一定有 f(1) = 1

• 欧拉定理

  欧拉定理指出，对于正整数 a, p ，若 \gcd(a, p) = 1 ，则：

  a^{\phi(n)}\equiv 1\pmod p

  费马小定理是欧拉定理的特例。

扩展欧拉定理指出，对于正整数 a, b, p ，有:

这可以在取模意义下帮我们有效控制指数的大小

• Lucas 定理

  Lucas 定理指出，对于非负整数 n, m 和素数 p ，有：

  \begin{pmatrix} n\\m \end{pmatrix} \equiv \begin{pmatrix} \lfloor n/p \rfloor\\\lfloor m/p \rfloor \end{pmatrix}\begin{pmatrix} n\bmod p\\m\mod p \end{pmatrix}\pmod p

  遇到组合数模小素数，通常是利用 Lucas 定理递归展开实现。

• 威尔逊定理

  威尔逊定理指出，大于 1 的整数 p 为素数的充要条件是：

  (p-1)!\equiv -1 \pmod p

总结

从古到今，数学都是一个非常重要的学科。我们要努力学习，将前人精华予以传承。

依旧\ 向理想的银河迈进