OI中的数论

一. 质数

概念

$\varphi(n)$ ： $1\sim n$ 中与 $n$ 互质的数的个数。
如果当 $a, b$ 互质时，有 $f(a\times b)=f(a)\times (b)$ 。那么称函数 $f$ 为积性函数。若 $f$ 是积性函数，且在算术基本定理中 $n=\prod_{i=1}^{m}p_{i}^{c_{i}}$ ，则显然 $f(n)=\prod_{i=1}^{m}f\left(p_{i}^{c_{i}}\right)$ 。

性质

$1\sim n$ 中质数的个数：约 $\dfrac{n}{\ln n}$ 。
欧拉函数
1. $\forall n>1,1 \sim n$ 中与 $n$ 互质的数的和为 $\dfrac{n}{2}\times\varphi(n)$ 。
  
  证明：因为 $\gcd(n,x)=gcd(n,n-x)$ ，所以 $1\sim n$ 中与 $n$ 互质的数总是成对出现，平均值为 $\dfrac{n}{2}$ ，总和为 $\dfrac{n}{2}\times\varphi(n)$ 。
2. 若 $a, b$ 互质, 则 $\varphi(a\times b)=\varphi(a)\times\varphi(b)$ 。
  
  证明：根据下文欧拉函数单点计算公式直接得出。
3. 设 $p$ 为质数，若 $p \mid n$ 且 $p^{2} \mid n$ ，则 $\varphi(n)=\varphi(\dfrac{n}{p})\times p$ .
  
  证明：由条件得 $n$ 与 $\dfrac{n}{p}$ 质因子种类相同，只是指数不同，将 $\varphi(n)$ 和 $\varphi(\dfrac{n}{p})$ 根据下文单点计算公式拆分发现他们的商为 $p$ 。
4. 设 $p$ 为质数，若 $p \mid n$ 但 $p^{2} \nmid n$ ，则 $\varphi(n)=\varphi(\dfrac{n}{p})\times(p-1)$ 。
  
  证明：由条件得 $p$ 与 $\dfrac{n}{p}$ 互质，由性质 2 可得 $\varphi(n)=\varphi(\dfrac{n}{p})\times\varphi(p)=\varphi(\dfrac{n}{p})\times(p-1)$ 。
5. $\sum_{d\mid n}\varphi(d)=n$ 。
  
  证明：设 $n,m$ 互质， $n=p_1^{c_1}p_2^{c_2}\cdots$ ， $m=p_1'^{~c_1'}p_2'^{~c_2'}\cdots$ 。
  
  $\begin{gather} \sum_{d\mid nm}\varphi(d)=\sum\limits_{i=0}^{c_1}\sum\limits_{j=0}^{c_2}\cdots\sum\limits_{k=0}^{c_1'}\sum\limits_{l=0}^{c_2'}\cdots\varphi(p_1^ip_2^j\cdots p_1'^{~k}p_2'^{~l}\cdots)\\ =\sum\limits_{i=0}^{c_1}\sum\limits_{j=0}^{c_2}\cdots\varphi(p_1^ip_2^j\cdots)\sum\limits_{k=0}^{c_1'}\sum\limits_{l=0}^{c_2'}\cdots\varphi(p_1'^{~k}p_2'^{~l}\cdots)\\ =\sum_{f\mid n}\varphi(f)\sum_{g\mid m}\varphi(g)\\ \end{gather}$
  
  所以 $\sum_{d\mid n}\varphi(d)$ 是积性函数。
  
  设 $n$ 的质因子种类共 $k$ 种。
  
  $\begin{gather} \sum_{d\mid n}\varphi(d)=\prod_{i=1}^{i\le k}\sum_{f\mid p_i^{c_i}}\varphi(f)\\ =\prod_{i=1}^{i\le k}\sum_{j=0}^{j\le c_i}\varphi(p_i^j)\\ \text{由等比数列求和公式可得}\sum_{j=0}^{j\le c_i}\varphi(p_i^j)=p_i^{c_i}\\ =\prod_{i=1}^{i\le k}p_i^{c_i}\\ =n\\ \end{gather}$

公式

单点计算公式： $\varphi(n)=n \times \dfrac{p_{1}-1}{p_{1}} \times \dfrac{p_{2}-1}{p_{2}} \times \cdots \times \dfrac{p_{m}-1}{p_{m}}=n \times \prod_{\text{质数} p \mid n}\left(1-\dfrac{1}{p}\right)$ 。

感性理解：对于 $n$ 的每个质因子 $p$ 来说， $1\sim n$ 中有这个质因子的数在所有数中的比例为 $\dfrac{1}{p}$ ，这部分肯定无法与 $n$ 互质，剩下 $\dfrac{p-1}{p}$ 可能与 $n$ 互质，这是考虑一个质因子的情况。考虑所有质因子的情况就是 $\prod_{\text{质数}p\mid n}\left(1-\dfrac{1}{p}\right)$ ，再乘上 $1\sim n$ 中整数个数。
递推式： $\varphi(p\times i)=\varphi(i)\times\begin{cases}p&(p\mid i)\\p-1&(p\nmid i)\end{cases}$ 。

由性质 3、4 可得。

代码

单点质数筛
- 试除法
区间质数筛
- 埃氏筛
- 线性筛
自由区间质数筛
- 双筛法（筛小素数再筛区间素数）
单点质因数分解
- 试除法
单点欧拉函数——质因数分解（求值公式）
区间欧拉函数——线性法（积性性质）
自由区间欧拉函数——双筛法（求值公式）

二. 约数

性质

$n$ 的约数个数上界： $2\sqrt{n}$ 。

试除法的推论。
$1\sim n$ 每个数约数个数的总和：约 $n\log n$ 。

倍数法的推论：

估算每个数的约数和比较难，可以反过来考虑每个数的贡献，即每个数会作为多少个数（ $1\sim n$ 内）的约数。

$1\sim n$ 的贡献分别是 $\dfrac{n}{1},\dfrac{n}{2},\dfrac{n}{3}\cdots\dfrac{n}{n}$ ，可发现个数约是 $n\log n$ 。
$0\sim 2\times 10^9$ 中约数个数最多的数的约数个数是 $1600$ 。

公式

正约数个数： $\left(c_{1}+1\right) \times\left(c_{2}+1\right) \times \cdots \times\left(c_{m}+1\right)=\prod_{i=1}^{m}\left(c_{i}+1\right)$ 。
正约数和： $\left(1+p_{1}+p_{1}^{2}+\cdots+p_{1}^{c_{1}}\right) \times\cdots \times\left(1+p_{m}+p_{m}^{2}+\cdots+p_{m}^{c_{m}}\right)=\prod_{i=1}^{m}\left(\sum_{j=0}^{c_{i}}\left(p_{i}\right)^{j}\right)$ 。

证明：使用组合数证明即可。

代码

$gcd~lcm$
单点约数筛
- 试除法
区间约数筛
- 倍数法（埃氏）

三. 余数

概念

对于 $\forall a \in[0, m-1]$ ，合 $\{a+k m\}(k \in \mathbb{Z})$ 的所有数模 $m$ 同余，余数都是 $a_{0}$ 该集合称为一个模 $m$ 的同余类，简记为 $\bar{a}$ 。
模 $m$ 的同余类一共有 $m$ 个，分别为 $\overline{0}, \overline{1}, \overline{2}, \cdots, \overline{m-1}$ 。它们构成 $m$ 的完全剩余系。
$1 \sim m$ 中与 $m$ 互质的数代表的同余类共有 $\varphi(m)$ 个，它们构成 $m$ 的简化剩余系。例如, 模 10 的简化剩余系为 $\{\overline{1}, \overline{3}, \overline{7}, \overline{9}\}$ 。

乘法封闭：集合中的任意两个元素进行乘法运算，得到的结果还在这个集合中。

简化剩余系的性质： $m$ 的简化剩余系关于 $m$ 乘法封闭。

证明：设 $m$ 的简化剩余系中两数为 $a,b$ ，则 $a\times b$ 也与 $m$ 互质，根据余数的性质， $a\times b\bmod m$ 也与 $m$ 互质。
若整数 $b, m$ 互质，并且 $b \mid a$ ，则存在一个整数 $x$ ，使得 $a / b \equiv a \times x(\bmod m)$ 。称 $x$ 为 $b$ 的模 $m$ 乘法逆元，记为 $b^{-1}(\bmod m)$ 。因为 $a / b \equiv a \times b^{-1} \equiv a / b \times b \times b^{-1}(\bmod m)$ ，所以 $b \times b^{-1} \equiv 1(\bmod m)$ 。

定理 / 公式

欧拉定理：若正整数 $x, n$ 互质，则 $x^{\varphi(n)} \equiv 1(\bmod n)$ ，其中 $\varphi(n)$ 为欧拉函数。

证明：设集合 $S$ 为 $n$ 的简化剩余系，记作 $\{\overline{a}_1,\overline{a}_2\cdots\overline{a}_{\varphi(n)}\}$ ， $T$ 为 $n$ 的简化剩余系中所有数乘上 $x$ 构成的集合，记作 $\{\overline{x\times a}_1,\overline{x\times a}_2\cdots \overline{x\times a}_{\varphi(n)}\}$ 。
1. 证明所有 $T$ 中元素都在 $S$ 中：
  
  因为 $x,n$ 互质，所以 $\gcd(x,n)=1$ ，所以 $\gcd(x\bmod n, n)=1$ 。又因为简化剩余系具有乘法封闭的性质，所以 $x\times a_i\in S$
2. 证明所有 $T$ 中元素在模意义下不重复：
  
  反证法。若 $a_i$ 和 $a_j$ 是 $S$ 中两个不同元素，且 $x\times a_i\equiv x\times a_j(\bmod n)$ ，则 $x\times(a_i-a_j)\equiv0(\bmod n)$ 。又因为 $x\not\equiv 0(\bmod n)$ ，所以 $a_i-a_j\equiv 0(\bmod n)$ ， $a_i\equiv a_j(\bmod n)$ 。矛盾。
3. 证明 $S=T$ ：
  
  因为 1 和 2，又因为 $S$ 、 $T$ 中元素数量相等，所以 $S=T$ 。
4. 证明定理：
  
  $\begin{gather} \because x^{\varphi(n)}a_1a_2\cdots a_{\varphi(n)}\equiv (xa_1)(xa_2)\cdots(xa_{\varphi(n)})\equiv a_1a_2\cdots a_{\varphi(n)}(\bmod n)\\ \therefore a^{\varphi(n)}\equiv 1(\bmod n)\\ \end{gather}$
费马小定理：若 $p$ 是质数，则对于任意整数 $a$ ，有 $a^{p} \equiv a(\bmod p)$ 。

欧拉定理中 $n$ 为质数，两边同乘 $a$ 的情况。
欧拉定理推论1：若正整数 $a, n$ 互质，则对于任意正整数 $b$ ，有 $a^{b} \equiv a^{b \bmod \varphi(n)}(\bmod n)$ 。

证明：设 $b=k\times \varphi(n)+r$ 。

$\begin{gather} \because a^b\equiv a^b(\bmod n),a^{\varphi(n)}\equiv 1(\bmod n)\\ \therefore a^b\times (1^{-1})^k\equiv a^b\times ((a^{\varphi(n)})^{-1})^k(\bmod n)\\ a^b\equiv a^{b \bmod \varphi(n)}(\bmod n)\\ \end{gather}$
欧拉定理推论2：当 $a, n$ 不一定互质且 $b>\varphi(n)$ 时, 有 $a^{b} \equiv a^{b \bmod \varphi(n)+\varphi(n)}(\bmod n)$ 。

证明：略。
裴蜀定理：对于任意整数 $a, b$ ，存在一对整数 $x, y$ ，满足 $a x+b y=\operatorname{gcd}(a, b)$ 。

证明：
1. $b=0$ 时，有 $\begin{cases}x=0\\y=1\end{cases}$ 满足。
2. $b>0$ 时。设 $b\times x'+(a\bmod b)\times y'=\gcd(b,a\bmod b)$ 。
  
  $b\times x'+(a-\left\lfloor \dfrac{a}{b}\right\rfloor\times b)\times y'=gcd(a,b)\\ a\times y'+b\times(x'-\left\lfloor\dfrac{a}{b}\right\rfloor\times y')=gcd(a,b)$
  
  所以，有 $\begin{cases}x=y'\\y=x'-\left\lfloor\dfrac{a}{b}\right\rfloor\times y'\end{cases}$ 满足。
方程 $a x+b y=c$ 的通解： $x=\frac{c}{d} x_{0}+k \frac{b}{d},\quad y=\frac{c}{d} y_{0}-k \frac{a}{d}(k \in \mathbb{Z})$ 。