专栏文章

简谈数论

FFish_Chen
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miow9qrq
此快照首次捕获于
2025/12/03 02:11
3 个月前
此快照最后确认于
2025/12/03 02:11
3 个月前
查看原文

数论篇

一、基本工作：了解数论

  • 数论是什么

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

二、整数除法

  • 数学表达

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

  • 取余运算与取模运算

取余运算同样是在做除法时求得的余数，不过它允许结果的符号与被除数相同。
取模运算的结果是在进行完整数除法后得到的余数。因计算机中数据绝大多数时候进行的是取模运算，所以我们后面一律用“取模运算”来表述。
我们通常把取模运算记作 a mod b=ra \bmod b = r

三、一些基本的公式

  • 基础公式

设 a mod b=ra\bmod b = r 则有：
取商： q=⌊ab⌋q = \lfloor \frac{a}{b} \rfloor
被除数逆运算（商乘除数加余数）： a=⌊ab⌋b+(a mod b) a=\lfloor \frac{a}{b} \rfloor b + (a\bmod b)
特别地，在MO（数学奥赛）中有高斯取整函数： [x] [x]

  • 整除的一些性质

如果 aa 能够整除 bb ，即 amod  b=0a\mod b=0 ，我们将其记作 b∣ab|a 。其中称 aa 是 bb 的倍数， bb 是 aa 的因数（约数）。
由此基础，我们可以发现：
  1. b∣ab|a 等价于存在整数 kk 使得 a=kba=kb
  2. 若 a∣b,c∣da|b,c|d ，则 ac∣bdac|bd
  3. 自反性： a∣aa|a
  4. 反对称性：若 a∣b,b∣aa|b,b|a ，则 a=ba=b
  5. 传递性：若 a∣b,b∣ca|b,b|c ，则 a∣ca|c
  6. 线性法：若 a∣b,a∣ca|b,a|c ，则 a∣(mb+nc)a|(mb+nc)
  7. 消去律：若 ma∣mbma|mb ，则 a∣ba|b
特别地， 1 是所有整数的约数， 0 是所有整数的倍数。

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

  • 定义

最大公因数：亦称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个。 a,ba,b 的最大公约数记为 (a,b)(a,b) 。
最小公倍数：两个或多个整数公有的倍数叫做它们的公倍数，其中除 0 以外最小的一个公倍数就叫做这几个整数的最小公倍。整数 a,ba,b 的最小公倍数记为 [a,b][a,b]
我们为了方便进行使用，在计算中使用 gcd⁡(a,b)\gcd(a,b) 代表 a,ba,b 的最大公因数；同时，以 lcm(a,b)lcm(a,b) 代表 a,ba,b 的最小公倍数。
特别地， gcd⁡(a,b)×lcm(a,b)=a×b\gcd(a,b)\times lcm(a,b)=a\times b

五、一些定理和公式

  • 求最大公因数

  1. 辗转相减法：当 a≥ba\ge b 时， gcd⁡(a,b)=gcd⁡(b,a−b)\gcd(a,b)=\gcd(b,a-b)
  2. 辗转相除法：当 gcd⁡(a,b)=gcd⁡(b,amod  b)\gcd(a,b)=\gcd(b,a\mod b)
  3. 更相减损术（求高精度 a,ba,b 的最大公因数）：
分三种情况：
一、若 a,ba,b 均为偶数，则 gcd⁡(a,b)=2gcd⁡(a2,b2)\gcd(a,b)=2\gcd(\frac{a}{2},\frac{b}{2})
二、若 a,ba,b 一个是奇数，一个是偶数（假使 aa 为奇数），则 gcd⁡(a,b)=gcd⁡(a2,b)\gcd(a,b)=\gcd(\frac{a}{2},b)
三、若 a,ba,b 均为奇数，则 gcd⁡(a,b)=gcd⁡(b,a−b)\gcd(a,b)=\gcd(b,a-b)

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

任何一个正整数 nn 都可以唯一表示如下形式：
n=∏i=1+∞piein=\prod\limits_{i=1}^{+\infty} p_i^{e_i}
其中 pip_i 是第 ii 个素数， eie^i 是非负整数。

  • 调和级数

调和级数 HnH_n 被定义为正整数的倒数和，即：
Hn=1+12+13+⋯+1n=∑i=1n1iH_n=1+\frac{1}{2}+\frac{1}{3}+\dots+\frac{1}{n}=\sum\limits_{i=1}^{n}\frac{1}{i}

  • 巴塞尔问题

求正整数的倒数平方和，即：
∑i=1+∞1i2\sum\limits_{i=1}^{+\infty}\frac{1}{i^2}
结果是 π26\frac{\pi^2}{6}

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

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

  • 欧拉筛法（线性筛）

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

  • 模运算

a+b≡(a mod p)+(b mod p)(modp)a+b\equiv(a\bmod p)+(b\bmod p) \pmod p a−b≡(a mod p)−(b mod p)(modp)a-b\equiv(a\bmod p)-(b\bmod p) \pmod p a×b≡(a mod p)×(b mod p)(modp)a\times b\equiv(a\bmod p)\times(b\bmod p) \pmod p

  • 光速幂

当底数 aa 和模数 pp 都确定时，令 B=⌈p⌉B=\lceil \sqrt p\rceil ，则有：
ab≡(aB)⌊bB⌋×abmod  B(modp)a^b\equiv(a^B)^{\lfloor\frac{b}{B}\rfloor}\times a^{b\mod B}\pmod p
可以做到 O(n)O(\sqrt n) 预处理， O(1)O(1) 查询 abmod  pa^b\mod p

  • 乘法逆元

乘法逆元的存在是为了在模意义下进行除法运算。
具体而言，对于模数 pp ，我们希望对 aa 找到一个数 xx ，满足：
a×x≡1(modp)a\times x\equiv 1 \pmod p
此时 xx 是 aa 在模 pp 意义下的乘法逆元，记为 a−1=xa^{-1}=x 但是这个数不一定存在，如 a=0a=0 的时候就一定不存在。而在模数 pp 是素数的情况下，对于 a=1,2,…,p−1a = 1,2,\dots,p-1 ，对应的乘法逆元 a−1a^{-1} 都是存在的。

  • 费马小定理

对于素数 pp 和 a=1,2,…,p−1a=1,2,\dots,p-1 ，有：
ap−1≡1(modp)a^{p-1}\equiv 1\pmod p
换言之：
a×ap−2≡1(modp)a\times a^{p-2}\equiv 1\pmod p
即 ap−2mod  pa^{p-2}\mod p 是 aa 的乘法逆元。

  • 线性递推

对于素数 pp 和 i=2,3…,p−1i=2,3\dots,p-1 ，有：
i−1≡−⌊pi⌋(pmod  i)−1(modp)i^{-1}\equiv -\lfloor\frac{p}{i}\rfloor(p\mod i)^{-1}\pmod p

  • 离线逆元

给大素数 pp 和 nn 个数 a1,a2,…,ana_1,a_2,\dots,a_n ，记 A=∏i=1naiA=\prod\limits_{i=1}^{n}a_i ，求出 A−1mod  pA^{-1}\mod p ，之后就有：
ai−1≡A−1(∏j=1i−1aj)(∏j=i+1naj)(modp)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
后面两个括号内的内容可以前后缀积处理。

  • 整除分块

对于一个整数 nn ，它除以 1∼n1\sim n 之间的数后的商，只有不超过 2n2\sqrt n 种，且每种商对应的除数是一段连续区间。
对于除数 x≤nx\le\sqrt n ，对应的 ⌊nx⌋\lfloor\frac{n}{x}\rfloor 最多有 n\sqrt n 个。
对于除数 x>nx > \sqrt n ，则有
⌊nx⌋≤nx<n\lfloor\frac{n}{x} \rfloor \le \frac{n}{x}<\sqrt n
不超过 n\sqrt n 种。
同时 ⌊nx⌋\lfloor\frac{n}{x}\rfloor 的值是非严格单调的，所以相同的 ⌊nx⌋\lfloor\frac{n}{x}\rfloor 对应的除数 xx 是连续的。
如果我们知道了 ⌊nx⌋=y\lfloor\frac{n}{x}\rfloor=y 的除数 xx 区间左端点 ll ，则可以直接计算出右端点 rr ：
r=⌊n⌊nl⌋⌋r=\left\lfloor{\frac{n}{\lfloor\frac{n}{l}\rfloor}}\right\rfloor
通过一个简单的循环，可以在 O(n)O(\sqrt n) 的时间复杂度内得到所有的的 ⌊nx⌋\lfloor\frac{n}{x}\rfloor 值和对应的区间，即整除分块。

  • 线性丢番图方程

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

  • 裴蜀定理

裴蜀定理指出，对于线性丢番图方程 ax+by=cax + by = c ，存在解的充要条件为 gcd⁡(a,b)∣c\gcd(a, b) | c
在模 g=gcd⁡(a,b)g = \gcd(a, b) 意义下看方程：
ax+by≡c(modg)ax + by \equiv c \pmod g 0×x+0×y≡c(modg)0 \times x + 0 \times y \equiv c \pmod g c≡0(modg)c \equiv 0 \pmod g
必要性得证。
充分性则由扩展欧几里得算法构造解给出。

  • 扩展欧几里得算法

构造线性丢番图方程 ax+by=gcd⁡(a,b)ax + by = \gcd(a, b) 的整数解。
不妨考虑辗转相除法的递归或迭代过程：
ax+by=ay′+b(x′−⌊ab⌋y′)ax + by=ay'+b\left(x'-\lfloor\frac{a}{b}\rfloor y'\right)
系数对齐可以得到递归或迭代公式：
{x=y′y=x′−⌊ab⌋y′\left\{ \begin{array}{c} x=y' \\ y=x'-\lfloor\frac{a}{b}\rfloor y' \end{array} \right.
而对于递归的边界 a=gcd⁡(a,b),b=0a = \gcd(a, b), b = 0 ，方程退化为：
gcd⁡(a,b)x=gcd⁡(a,b)\gcd(a, b)x = \gcd(a, b)
由此可得解 x=1,y=0x = 1, y = 0
要求线性丢番图方程 ax+by=cax + by = c 的特解，把 ax+by=gcd⁡(a,b)ax + by = \gcd(a, b) 的 特解乘上 cgcd⁡(a,b)\frac{c}{\gcd(a,b)}

  • 中国剩余定理（CRT）

我们想要求解如下的线性同余方程组：
{x≡a1(modm1)x≡a2(modm2)⋮x≡an(modmn) \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.
中国剩余定理指出，在 m1,m2,…,mnm_1,m_2,\dots,m_n 两两互素的情况下的解：
x=kM+∑i=1naiMitix=kM+\sum\limits_{i=1}^{n}a_iM_it_i M=∏i=1nmi,Mi=MmiM=\prod\limits_{i=1}^{n}m_i,M_i=\frac{M}{m_i} ti=Mi−1 mod mit_i=M_i^{-1}\bmod m_i
扩展：假设有一个解 x0x_0 ，则其通解为：
x≡x0+klcm(m1,m2)x\equiv x_0+klcm(m_1,m_2)
实际上就是合并成为新的线性同余方程：
x≡x0(modlcm(m1,m2))x\equiv x_0\pmod {lcm(m_1,m_2)}

  • 欧拉函数

欧拉函数 ϕ(n)\phi(n) 定义为 1∼n1 \sim n 中与 nn 互素的数的个数，即：
ϕ(n)=∑i=1n[gcd⁡(n,i)=1]\phi(n)=\sum\limits_{i=1}^{n}[\gcd(n,i)=1]
简化式子可得：
ϕ(n)=n∏i=1k(1−1pi)\phi(n)=n\prod\limits_{i=1}^{k}\left(1-\frac{1}{p_i}\right)

  • 积性函数

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

  • 欧拉定理

欧拉定理指出，对于正整数 a,pa, p ，若 gcd⁡(a,p)=1\gcd(a, p) = 1 ，则：
aϕ(n)≡1(modp)a^{\phi(n)}\equiv 1\pmod p
费马小定理是欧拉定理的特例。
扩展欧拉定理指出，对于正整数 a,b,pa, b, p ，有:
ab={ab                     b<ϕ(p)                                     (modp)ab mod ϕ(p)+ϕ(p) b≥ϕ(p)a^b=\left\{ \begin{array}{c} a^b \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ b<\phi(p) \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \pmod p\\ a^{b \bmod\phi(p)+\phi(p)} \ b \ge \phi(p)\end{array} \right.
这可以在取模意义下帮我们有效控制指数的大小

  • Lucas 定理

Lucas 定理指出，对于非负整数 n,mn, m 和素数 pp ，有：
(nm)≡(⌊n/p⌋⌊m/p⌋)(n mod pmmod  p)(modp)\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 定理递归展开实现。

  • 威尔逊定理

威尔逊定理指出，大于 11 的整数 pp 为素数的充要条件是：
(p−1)!≡−1(modp)(p-1)!\equiv -1 \pmod p

总结

从古到今，数学都是一个非常重要的学科。我们要努力学习，将前人精华予以传承。
依旧
向理想的银河迈进

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...