提高级-数学-初等数论-同余、欧拉定理、欧拉函数、费马小定理、裴蜀定理

# 同余

----

## 同余的定义

设整数 $m\ne 0$。若 $m\mid(a-b)$，称 $m$ 为 **模数**（**模**），$a$ 同余于 $b$ 模 $m$，$b$ 是 $a$ 对模 $m$ 的 **剩余**。记作 $a\equiv b\pmod m$。
    
否则，$a$ 不同余于 $b$ 模 $m$，$b$ 不是 $a$ 对模 $m$ 的剩余。记作 $a\not\equiv b\pmod m$。
    
这样的等式，称为模 $m$ 的同余式，简称 **同余式**。

根据整除的性质，上述同余式也等价于 $a\equiv b\pmod{(-m)}$。

**如果没有特别说明，模数总是正整数。**

式中的 $b$ 是 $a$ 对模 $m$ 的剩余，这个概念与余数完全一致。通过限定 $b$ 的范围，相应的有 $a$ 对模 $m$ 的最小非负剩余、绝对最小剩余、最小正剩余。

----

### 同余的性质

-   同余是 [等价关系](../order-theory.md#二元关系)，即同余具有
    -   自反性：$a\equiv a\pmod m$。
    -   对称性：若 $a\equiv b\pmod m$，则 $b\equiv a\pmod m$。
    -   传递性：若 $a\equiv b\pmod m,b\equiv c\pmod m$，则 $a\equiv c\pmod m$。
----

-   线性运算：若 $a,b,c,d\in\mathbf{Z},m\in\mathbf{N}^*,a\equiv b\pmod m,c\equiv d\pmod m$ 则有：
    -   $a\pm c\equiv b\pm d\pmod m$。
    -   $a\times c\equiv b\times d\pmod m$。

----

-   设 $f(x)=\sum_{i=0}^n a_ix^i$ 和 $g(x)=\sum_{i=0}^n b_ix^i$ 是两个整系数多项式，$m\in\mathbf{N}^*$，且 $a_i\equiv b_i\pmod m,~0\leq i\leq n$，则对任意整数 $x$ 均有 $f(x)\equiv g(x)\pmod m$。进而若 $s\equiv t\pmod m$，则 $f(s)\equiv g(t)\pmod m$。
-   若 $a,b\in\mathbf{Z},k,m\in\mathbf{N}^*,a\equiv b\pmod m$, 则 $ak\equiv bk\pmod{mk}$。
-   若 $a,b\in\mathbf{Z},d,m\in\mathbf{N}^*,d\mid a,d\mid b,d\mid m$，则当 $a\equiv b\pmod m$ 成立时，有 $\dfrac{a}{d}\equiv\dfrac{b}{d}\left(\bmod\;{\dfrac{m}{d}}\right)$。
-   若 $a,b\in\mathbf{Z},d,m\in\mathbf{N}^*,d\mid m$，则当 $a\equiv b\pmod m$ 成立时，有 $a\equiv b\pmod d$。
-   若 $a,b\in\mathbf{Z},d,m\in\mathbf{N}^*$，则当 $a\equiv b\pmod m$ 成立时，有 $(a,m)=(b,m)$。若 $d$ 能整除 $m$ 及 $a,b$ 中的一个，则 $d$ 必定能整除 $a,b$ 中的另一个。

----

还有性质是乘法逆元。

---

# 费马小定理

----

### 定义

若 $p$ 为素数，$\gcd(a, p) = 1$，则 $a^{p - 1} \equiv 1 \pmod{p}$。

另一个形式：对于任意整数 $a$，有 $a^p \equiv a \pmod{p}$。

----

### 证明

设一个质数为 $p$，我们取一个不为 $p$ 倍数的数 $a$。

构造一个序列：$A=\{1,2,3\dots,p-1\}$，这个序列有着这样一个性质：

$$
\prod_{i=1}^{p-1}\space A_i\equiv\prod_{i=1}^{p-1} (A_i\times a) \pmod p
$$

----

证明：

$$
\because (A_i,p)=1,(A_i\times a,p)=1
$$

又因为每一个 $A_i\times a \pmod p$ 都是独一无二的，且 $A_i\times a \pmod p < p$

得证（每一个 $A_i\times a$ 都对应了一个 $A_i$）

设 $f=(p-1)!$, 则 $f\equiv a\times A_1\times a\times A_2\times a \times A_3 \dots \times  A_{p-1} \pmod p$

$$
\begin{aligned}
a^{p-1}\times f &\equiv f \pmod p \\
a^{p-1} &\equiv 1 \pmod p
\end{aligned}
$$

证毕。

----

也可用归纳法证明：

显然 $1^p\equiv 1\pmod p$，假设 $a^p\equiv a\pmod p$ 成立，那么通过二项式定理有

$$
(a+1)^p=a^p+\binom{p}{1}a^{p-1}+\binom{p}{2}a^{p-2}+\cdots +\binom{p}{p-1}a+1
$$

因为 $\binom{p}{k}=\frac{p(p-1)\cdots (p-k+1)}{k!}$ 对于 $1\leq k\leq p-1$ 成立，在模 $p$ 意义下 $\binom{p}{1}\equiv \binom{p}{2}\equiv \cdots \equiv \binom{p}{p-1}\equiv 0\pmod p$，那么 $(a+1)^p \equiv a^p +1\pmod p$，将 $a^p\equiv a\pmod p$ 带入得 $(a+1)^p\equiv a+1\pmod p$ 得证。

---

# 欧拉函数

----

## 定义

欧拉函数（Euler's totient function），即 $\varphi(n)$，表示的是小于等于 $n$ 和 $n$ 互质的数的个数。

比如说 $\varphi(1) = 1$。

当 $n$ 是质数的时候，显然有 $\varphi(n) = n - 1$。

----

## 性质

-   欧拉函数是 [积性函数](./basic.md#积性函数)。

即对任意满足 $\gcd(a, b) = 1$ 的整数 $a,b$，有 $\varphi(ab) = \varphi(a)\varphi(b)$。

特别地，当 $n$ 是奇数时 $\varphi(2n) = \varphi(n)$。
-   $n = \sum_{d \mid n}{\varphi(d)}$。
-   若 $n = p^k$，其中 $p$ 是质数，那么 $\varphi(n) = p^k - p^{k - 1}$。
    （根据定义可知）

-   由唯一分解定理，设 $n = \prod_{i=1}^{s}p_i^{k_i}$，其中 $p_i$ 是质数，有 $\varphi(n) = n \times \prod_{i = 1}^s{\dfrac{p_i - 1}{p_i}}$。

----

### 证明
-   引理：设 $p$ 为任意质数，那么 $\varphi(p^k)=p^{k-1}\times(p-1)$。
        
证明：显然对于从 1 到 $p^k$ 的所有数中，除了 $p^{k-1}$ 个 $p$ 的倍数以外其它数都与 $p^k$ 互素，故 $\varphi(p^k)=p^k-p^{k-1}=p^{k-1}\times(p-1)$，证毕。

----
 
接下来我们证明 $\varphi(n) = n \times \prod_{i = 1}^s{\dfrac{p_i - 1}{p_i}}$。由唯一分解定理与 $\varphi(x)$ 函数的积性
$$
\begin{aligned}
    \varphi(n) &= \prod_{i=1}^{s} \varphi(p_i^{k_i}) \\
    &= \prod_{i=1}^{s} (p_i-1)\times {p_i}^{k_i-1}\\
    &=\prod_{i=1}^{s} {p_i}^{k_i} \times(1 - \frac{1}{p_i})\\
    &=n~ \prod_{i=1}^{s} (1- \frac{1}{p_i})
    &\square
\end{aligned}
$$

-   对任意不全为 $0$ 的整数 $m,n$，$\varphi(mn)\varphi(\gcd(m,n))=\varphi(m)\varphi(n)\gcd(m,n)$。

可由上一条直接计算得出。

----

## 实现

如果只要求一个数的欧拉函数值，那么直接根据定义质因数分解的同时求就好了。这个过程可以用 [Pollard Rho](./pollard-rho.md) 算法优化。

```cpp
#include <cmath>

int euler_phi(int n) {
  int ans = n;
  for (int i = 2; i * i <= n; i++)
    if (n % i == 0) {
      ans = ans / i * (i - 1);
      while (n % i == 0) n /= i;
    }
  if (n > 1) ans = ans / n * (n - 1);
  return ans;
}
```

如果是多个数的欧拉函数值，可以利用后面会提到的线性筛法来求得。

----

## 应用

欧拉函数常常用于化简一列最大公约数的和。国内有些文章称它为 **欧拉反演**[^1]。

在结论

$$
n=\sum_{d|n}\varphi(d)
$$

中代入 $n=\gcd(a,b)$，则有

$$
\gcd(a,b) = \sum_{d|\gcd(a,b)}\varphi(d) = \sum_d [d|a][d|b]\varphi(d),
$$

----

其中，$[\cdot]$ 称为 [Iverson 括号](https://mathworld.wolfram.com/IversonBracket.html)，只有当命题 $P$ 为真时 $[P]$ 取值为 $1$，否则取 $0$。对上式求和，就可以得到

$$
\sum_{i=1}^n\gcd(i,n)=\sum_{d}\sum_{i=1}^n[d|i][d|n]\varphi(d)=\sum_d\left\lfloor\frac{n}{d}\right\rfloor[d|n]\varphi(d)=\sum_{d|n}\left\lfloor\frac{n}{d}\right\rfloor\varphi(d).
$$

这里关键的观察是 $\sum_{i=1}^n[d|i]=\lfloor\frac{n}{d}\rfloor$，即在 $1$ 和 $n$ 之间能够被 $d$ 整除的 $i$ 的个数是 $\lfloor\frac{n}{d}\rfloor$。

利用这个式子，就可以遍历约数求和了。需要多组查询的时候，可以预处理欧拉函数的前缀和，利用数论分块查询。

----

[GCD SUM](https://www.luogu.com.cn/problem/P2398)
给定 $n\le 100000$，求

$$
\sum_{i=1}^n\sum_{j=1}^n\gcd(i,j).
$$

### 思路

仿照上文的推导，可以得出
    
$$
\sum_{i=1}^n\sum_{j=1}^n\gcd(i,j) = \sum_{d=1}^n\left\lfloor\frac{n}{d}\right\rfloor^2\varphi(d).
$$
        
此时需要从 $1$ 遍历到 $n$ 求欧拉函数，用线性筛做就可以 $O(n)$ 得到答案。

---

# 欧拉定理

----

### 定义

若 $\gcd(a, m) = 1$，则 $a^{\varphi(m)} \equiv 1 \pmod{m}$。

----

### 证明

实际上这个证明过程跟上文费马小定理的证明过程是非常相似的：**构造一个与 $m$ 互质的数列**，再进行操作。

设 $r_1, r_2, \cdots, r_{\varphi(m)}$ 为模 $m$ 意义下的一个简化剩余系，则 $ar_1, ar_2, \cdots, ar_{\varphi(m)}$ 也为模 $m$ 意义下的一个简化剩余系。所以 $r_1r_2 \cdots r_{\varphi(m)} \equiv ar_1 \cdot ar_2 \cdots ar_{\varphi(m)} \equiv a^{\varphi(m)}r_1r_2 \cdots r_{\varphi(m)} \pmod{m}$，可约去 $r_1r_2 \cdots r_{\varphi(m)}$，即得 $a^{\varphi(m)} \equiv 1 \pmod{m}$。

当 $m$ 为素数时，由于 $\varphi(m) = m - 1$，代入欧拉定理可立即得到费马小定理。

---
# 裴蜀定理

裴蜀定理，又称贝祖定理（Bézout's lemma）、贝祖等式（Bézout's identity），是一个关于最大公约数的定理。

其内容是：

设 $a,b$ 是不全为零的整数，对任意整数 $x,y$，满足 $\gcd(a,b)\mid ax+by$，且存在整数 $x,y$, 使得 $ax+by=\gcd(a,b)$.

----

## 证明

对于第一点

由于 $\gcd(a,b)\mid a,\gcd(a,b)\mid b$

所以 $\gcd(a,b)\mid ax,\gcd(a,b)\mid by$，其中 $x,y$ 均为整数

因此 $\gcd(a,b)\mid ax+by$

----

对于第二点

1.  若任何一个等于 $0$, 则 $\gcd(a,b)=a$. 这时定理显然成立。

2.  若 $a,b$ 不等于 $0$.

由于 $\gcd(a,b)=\gcd(a,-b)$,

不妨设 $a,b$ 都大于 $0$，$a\geq b,\gcd(a,b)=d$.

对 $ax+by=d$, 两边同时除以 $d$, 可得 $a_1x+b_1y=1$, 其中 $(a_1,b_1)=1$.

----

转证 $a_1x+b_1y=1$.

我们先回顾一下辗转相除法是怎么做的，由 $\gcd(a, b) \rightarrow \gcd(b,a\mod b) \rightarrow \dots$ 我们把模出来的数据叫做 $r$ 于是，有

$$
    \gcd(a_1,b_1)=\gcd(b_1,r_1)=\gcd(r_1,r_2)=\cdots=(r_{n-1},r_n)=1
    $$

把辗转相除法中的运算展开，做成带余数的除法，得

$$
    \begin{aligned}a_1 &= q_1b_1+r_1 &(0\leq r_1<b_1) \\ b_1 &= q_2r_1+r_2 &(0\leq r_2<r_1) \\ r_1 &= q_3r_2+r_3 &(0\leq r_3<r_2) \\ &\cdots \\ r_{n-3} &= q_{n-1}r_{n-2}+r_{n-1} \\ r_{n-2} &= q_nr_{n-1}+r_n \\ r_{n-1} &= q_{n+1}r_n\end{aligned}
    $$

----

不妨令辗转相除法在除到互质的时候退出则 $r_n=1$ 所以有（$q$ 被换成了 $x$，为了符合最终形式）

$$
    r_{n-2}=x_nr_{n-1}+1
    $$

即

$$
    1=r_{n-2}-x_nr_{n-1}
    $$

由倒数第三个式子 $r_{n-1}=r_{n-3}-x_{n-1}r_{n-2}$ 代入上式，得

$$
    1=(1+x_nx_{n-1})r_{n-2}-x_nr_{n-3}
    $$

然后用同样的办法用它上面的等式逐个地消去 $r_{n-2},\cdots,r_1$,

可证得 $1=a_1x+b_1y$.
    这样等于是一般式中 $d=1$ 的情况。

----

## 推广

### 逆定理

设 $a, b$ 是不全为零的整数，若 $d > 0$ 是 $a, b$ 的公因数，且存在整数 $x, y$, 使得 $ax+by=d$，则 $d = \gcd(a, b)$。

特殊地，设 $a, b$ 是不全为零的整数，若存在整数 $x, y$, 使得 $ax+by=1$，则 $a, b$ 互质。

----

### 多个整数

裴蜀定理可以推广到 $n$ 个整数的情形：设 $a_1, a_2, \dots, a_n$ 是不全为零的整数，则存在整数 $x_1, x_2, \dots, x_n$, 使得 $a_1 x_1 + a_2 x_2 + \cdots + a_n x_n=\gcd(a_1, a_2, \dots, a_n)$。其逆定理也成立：设 $a_1, a_2, \dots, a_n$ 是不全为零的整数，$d > 0$ 是 $a_1, a_2, \dots, a_n$ 的公因数，若存在整数 $x_1, x_2, \dots, x_n$, 使得 $a_1 x_1 + a_2 x_2 + \cdots + a_n x_n=d$，则 $d = \gcd(a_1, a_2, \dots, a_n)$。

----

## 应用

Codeforces Round #290 (Div. 2) D. Fox And Jumping

给出 $n$ 张卡片，分别有 $l_i$ 和 $c_i$。在一条无限长的纸带上，你可以选择花 $c_i$ 的钱来购买卡片 $i$，从此以后可以向左或向右跳 $l_i$ 个单位。问你至少花多少元钱才能够跳到纸带上全部位置。若不行，输出 $-1$。

----

分析该问题，发现想要跳到每一个格子上，必须使得所选数 $l_{i_1}, \dots, l_{i_k}$ 通过数次相加或相减得出的绝对值为 $1$，也即存在整数 $x_1, \dots, x_n$ 使得 $l_{i_1} x_1 + \cdots + l_{i_k} x_k = 1$。由多个整数的裴蜀定理逆定理，这相当于从数组 $l_1, \dots, l_n$ 选择若干个数，满足它们的最大公因数为 1，同时要求代价和最小。

**解法 1**：我们可以转移思想，因为这些数互质，即为 $0$ 号节点开始，每走一步求 $\gcd$（节点号，下一个节点），同时记录代价（求边权），就成为了从 $0$ 通过不断 $\gcd$ 最后变为 $1$ 的最小代价。

由于：互质即为最大公因数为 $1$，$\gcd(0,x)=x$ 这两个定理，可以证明该算法的正确。选择优先队列优化 Dijkstra 求解。

不过还有个问题，即为需要记录是否已经买过一个卡片，开数组标记由于数据范围达到 $10^9$ 会超出内存限制，可以想到使用 `unordered_map`（比普通的 `map` 更快地访问各个元素，迭代效率较低，详见 [STL-map](../../lang/csl/associative-container.md)）

----

**解法 2**：从数组 $l_1, \dots, l_n$ 选择若干个数，满足它们的最大公因数为 1，且代价和最小，由此可以想到 0-1 背包问题。

设 $f_{i, j}$ 表示考虑前 $i$ 个数且最大公因数为 $j$ 的最小代价，则有转移方程：

$$
f_{i, j} = \min_{\gcd(k, l_i) = j} f_{i - 1, k} + c_i.
$$

DP 后最终的总代价即为 $f_{n, 1}$。

如同一般的 0-1 背包问题，可以用滚动数组优化，去掉第一维。而这里 300 个数可达的最大公因数 $j$ 是很稀疏的，因此还可以使用 `unordered_map` 代替数组储存下标 $j$，优化内存并进一步减少枚举量。

实际上，这里解法 1 建出的图便是解法 2 中动态规划的状态转移图，解法 2 相当于用动态规划求有向无环图的最短路，因此解法 1 和解法 2 是等价的。但解法 2 无需储存全图，同时 DP 的时间复杂度为 $O(n + m)$，相比 Dijkstra 算法更低，因此解法 2 在时间和空间上更优。

----

## 进一步结论

对自然数 $a$、$b$ 和整数 $n$，$a$ 与 $b$ 互素，考察不定方程：

$$
ax+by=n
$$

其中 $x$ 和 $y$ 为自然数。如果方程有解，称 $n$ 可以被 $a$、$b$ 表示。

记 $C=ab-a-b$。由 $a$ 与 $b$ 互素，$C$ 必然为奇数。则有结论：

**对任意的整数 $n$，$n$ 与 $C-n$ 中有且仅有一个可以被表示。**

即：可表示的数与不可表示的数在区间 $[0,C]$ 对称（关于 $C$ 的一半对称）。$0$ 可被表示，$C$ 不可被表示；负数不可被表示，大于 $C$ 的数可被表示。

----

### 证明

由于 $a$、$b$ 互素，因此原方程有整数解。设解为：

$$
\begin{cases} x=x_0+bt\\\\y=y_0-at\end{cases}
$$

其中 $t$ 为整数。取适当的 $t$，使得 $y$ 位于 $0$ 到 $a-1$ 之间。这只需在 $y_0$ 上加上或减去若干个 $a$，即可得到这样的 $t$。

----

第一步：证明大于 $C$ 的数都可以被表示。当 $n$ 大于 $C$ 时：

$$
ax=n-by>ab-a-b-by\geqslant ab-a-b-b(a-1)=-a
$$

于是 $x$ 也是非负整数。

----

第二步：证明 $C$ 不可被表示，进而 $n$ 与 $C-n$ 不可能都被表示。

反证法。若 $ax+by=ab-a-b$ 有非负整数解 $x$、$y$，则：

$$
ab=a(x+1)+b(y+1)
$$

由于 $a$ 与 $b$ 互素，所以 $a$ 整除 $y+1$，$b$ 整除 $x+1$，$a$ 不超过 $y+1$，$b$ 不超过 $x+1$。于是有：

$$
ab=a(x+1)+b(y+1)\geqslant ab+ab=2ab
$$

矛盾！第二步证完。

----

第三步：证明如果 $n$ 不可被表示，则 $C-n$ 可被表示。

由上可知，若 $n$ 不可被表示，由于上述方程中已规定 $y$ 在 $0$ 到 $a-1$ 之间，则 $x$ 为负。所以：

$$
ab-a-b-ax-by=a(-x-1)+b(a-1-y)
$$

显然 $-x-1$ 和 $a-1-y$ 均非负，于是 $C-n$ 可被表示。

----

### 几何意义

重新观察方程 $ax+by=n$，将它看成一条直线。直线与两坐标轴在第一象限围成三角形。

当 $n<ab$ 的时候，这个直线在第一象限，至多只能通过一个整点。

根据上述讨论：当 $n$ 可以被表示的时候，直线恰好经过一个整点；当 $n$ 不可以被表示的时候，直线不经过整点（在第一象限）。

这结论也可以理解为：作三角形 $(0,0)(b,0)(0,a)$。随着 $n$ 从 $0$ 不断增加，直线向右上方平移，整点会一个一个地通过直线，直到最后才撞上两个整点。

因此，小于等于 $n$ 的能被表示的非负整数的数量，恰好就是直线 $ax+by=n$（含）与两坐标轴（含）在第一象限围成三角形覆盖的整点个数。

----

### 另一种解释

考虑模 $b$ 意义下每个剩余系中最小能被表示的值是多少——大于他们的可以通过增加若干个 $b$ 得到。

观察原方程，$a$ 的若干倍数 $0, a,\cdots, (b−1)a$ 在 $\pmod b$ 意义下互不相同。这些数恰好是这些最小值。那么当 $n<ab$ 时，小于等于 $n$ 的能被表示的非负整数的数量是：

$$
\sum\limits_{i=0}^{\left[\frac{n}{a}\right]}\left[\frac{n − ia}{b}\right]
$$

----

这是一个非常经典的直线下整点问题，恰好是这条直线：

$$
y=-\frac{a}{b}x+\frac{n}{b}
$$

即 $ax+by=n$。

使用类欧几里得算法可以在 $O(\log \max(a,b))$ 的时间内求解。因此我们得到了计算小于等于 $n$ 的能被表示的非负整数的数量的工具。

----

### 题目

[P3951 NOIP2017 提高组 小凯的疑惑/蓝桥杯 2013 省 买不到的数目](https://www.luogu.com.cn/problem/P3951)