本期主要内容：整除性、模运算性质、唯一分解定理、拓展欧几里得算法、乘法逆元、威尔逊定理、费马小定理、二次剩余。

因为这只是我自己的笔记，因此我会补充一些必要的证明过程，但考虑到效率问题，不会把所有的概念都讲成白话。

emmm……这篇文章似乎鸽了很久。

整除性质

定义：若 $a \div b = m … k$, 则 $a/b = m$ ($m$ 是 $a, b$ 的商)、$a \mod b = k$, $k$ 是余数。
定理：对于 $\forall a, b \in N^{*}$, $a$ 可以被唯一表示成 $m \times b + k$ 的形式，其中 $0 \leq k < b$.

根据上述有关乘除的定理，我们可以推导出以下性质（下面默认 $a, b \in N^*$）：

• 若 $a \times b \leq c$, 则 $a \leq \lfloor{\frac{c}{b}}\rfloor$

证明：将 $c$ 表示为 $c = mb + p (p \lt b)$
则由 $a \leq \frac{c}{b}$ 得到 $a \leq m + \frac{p}{b}$
又 $\lfloor \frac{c}{b} \rfloor = m$，$a \in N^*$ 且 $\frac{p}{b} \in [0, 1)$
所以 $a \leq m$，从而 $a \leq \lfloor \frac{c}{b}\rfloor$，证毕。

上述定理的必要性也成立:

• 若 $a \leq \lfloor \frac{c}{b} \rfloor, 则 a \times b \leq c$.

证明: 将 $c$ 表示为 $mb + p(p < b)$，则 $a \leq m$
那么 $a \times b \leq m \times b \leq m \times b + p = c$, 证毕。

• 若 $a \times b \geq c$, 则 $a \geq \lfloor\frac{c}{b}\rfloor$.

证明：将 $c$ 表示为 $mb + p(p < b)$，则 $a \times b \geq mb + p$
即 $a \geq m + \frac{p}{b}$
显然 $\lfloor \frac{c}{b} \rfloor = m \leq m + \frac{p}{b}.$

但上述定理的必要性：若 $a \geq \lfloor \frac{c}{b} \rfloor$，则 $a \times b \geq c$ 是不成立的。

证明：假设上述定理成立，将 $c$ 表示为 $mb + p$
则 $a \geq m$，当 $p \geq 0$ 时，
由 $a \times b \geq mb$，$mb \lt mb + p = c$.
故上式不成立。

• $a / b / c = a / (b * c) = a / c / b$, 其中 $/$ 是整除符号。

证明：设 $a = k(b \times c) +t$, 则:
$a/b/c = kc/c = k$
$a / (b * c) = k$
$a/c/b = kb/b = k$
证毕。

模运算性质

模运算的性质可以说是很基础的东西了：

• $(a + b) \mod n = (a \mod n + b \mod n) \mod n$
• $(a - b) \mod n = (a \mod n - b \mod n) \mod n$

注意，因为在 C++ 中的取模运算规则是向零取模，所以上面的式子在 C++ 中应用时应该被变形为： $(a - b) \mod n = (a \mod n - b \mod n + n) \mod n$.

• $(a \times b) \mod n = [(a \mod n) \times (b \mod n)] \mod n$

上述定律不可推广到除法。但有如下推论：

• $[(a \times n) \mod (b \times n)] = (a \mod b) \times n$.

最大公因数

设有正整数 $a, b (a \ge b)$, 定义 $gcd(a, b)$ 为 $a, b$ 的最大公约数 (greatest common divisor). 我们约定 $gcd(n, 0) = n$.

求两个数最大公因数的方式一般有两种：

更相减损术：$gcd(a, b) = gcd(b, a-b) = …$, 这种方法用于求两个高精度数的最大公约数很有效（因为高精度的除法不易实现）。但如果遇到一个数很大，另一个数比较小的情况，该算法的复杂度可能会退化到 $O(n)$.

int gcd(int a, int b) {
    if (b == 0)
        return a;
    if (a < b)
        std::swap(a, b);
    return gcd(b, a - b);
}

欧几里得算法（辗转相除法）：$gcd(a, b) = gcd(b, b \mod a)$，该算法的复杂度是稳定为 $O(logn)$ 的，所以平时求 GCD 较多采用这种方法。

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

拓展欧几里得算法 (exgcd)

再把旧的东西复习一遍吧。对于不全为零的非负整数 $a, b$ 和等式 $ax + by = gcd(a, b)$，我们可以用拓展欧几里得算法（exgcd）来求 $x, y$ 的一组可行解。

原理很简单：因为 $gcd(a, b) = gcd(b, a \mod b)$，所以有方程组

$$\begin{cases} ax_1 + by_1 = gcd(a, b) = m \\ bx_2 + (a \mod b)y_2 = gcd(b, a \mod b) = m\end{cases}$$.

而对于上述方程组整理得到等式

$$ ax_1 + by_1 = bx_2 + (a \mod b)y_2 $$.

根据上文对整除和余数的定义，因为 $a \mod b = a - \lfloor\frac{a}{b}\rfloor\cdot b$，所以上面的式子化为：

$$ ax_1 + by_1 = bx_2 + (a - [a \div b] \cdot b)y_2 $$

即

$$ax_1 + by_1 = ay_2 + b(x_2 - [a \div b] y_2)$$

根据方程对应系数的关系，得到方程组 (*)：

$$\begin{cases} x_1 = y_2 \\ y_1 = (x_2 - [a \div b] y_2) \end{cases}$$

我们要求的是 $x, y$ 的一组解，也就是说所求是 $x_1, y_1$. 那么，我们只要知道了 $x_2, y_2$ 即可推出 $x_1, y_1$. 根据上面的规则，我们可以得到递推方程组：

$$\begin{cases} bx_2 + (a \mod b)y_2 = gcd(b, a \mod b) = m \\(a \mod b) x_3 + (b \mod (a \mod b))y_3 = gcd(a \mod b, b \mod (a \mod b)) = m \end{cases}$$

因为最终上述递推方程 $a’x+b’y = gcd(a’, b’)$ 中，$b’ = 0$，此时 $gcd(a’, b’) = a’$，显然有$x=1, y=*$ 是方程的一组解，我们这里取 $x = 1, y = 0$. 层层回溯即可得到 $x_1, y_1$.

exgcd 算法的关键在于理解并记住递推关系方程组 (*)，理解之后主程序就好写了。

int x, y;
void exgcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1, y = 0;
        return;
    }
    exgcd(b, a % b);
    int tmp = x;
    x = y;
    y = tmp - (a / b) * y;
}

exgcd 可以用于：(1) 求解二元一次方程 $ax + by = c$. 设 $gcd(a, b) = d$，那么上述方程有解的充要条件是 $d$ 是 $c$ 的约数，即 $c = nd$. 使用 exgcd 求出一组可行解 $x_1, y_1$ 后将其乘以系数 $\frac{c}{d}$ 即可，即原方程的一组解为：

$$\begin{cases}x = x_1 \cdot \frac{c}{d} \\ y = y_1 \cdot \frac{c}{d} \end{cases}$$

(2) 求解乘法逆元。

乘法逆元

首先引入同余这一概念，顾名思义——同余就是相同余数的意思。

同余：对于两个整数 $a, b$ 和正整数 $k$, 如果 $a \mod k = n$, $b \mod k = n$，也就是说 $a, b$ 除 $k$ 的整数相同都是 $n$, 此时我们称 $a, b$ 在模 $k$ 的意义下同余，记作 $a \equiv b (\mod k)$.

接下来引入乘法逆元的概念：

乘法逆元：如果 $ax$ 与 $1$ 在模 $p$ 的意义下同余，也就是说 $ax \mod p = 1 \mod p, ax \equiv 1(\mod p)$, 并且 $a, p$ 互为质数（即 $gcd(a, p) = 1$），那么我们定义：$x$ 是 $a$ 关于模 $p$ 的乘法逆元。$x$ 在模 $p$ 的意义下是唯一的，即 $0 \leq x \leq p-1$ 时，逆元 $x$ 是惟一的。

怎么理解？在实数意义下，非零实数 $a$ 与非零实数 $\frac{1}{a}$ 相乘的结果为 1；但是在模某一个数 $p$ 意义下，满足 $ax \mod p = 1 \mod p$ 的数 $x$ 并不一定是 $\frac{1}{a}$，而可能是一个其它整数，这个整数就称为乘法逆元。

求逆元的方法之一：使用 exgcd 来求乘法逆元。为什么可以用 exgcd 求逆元呢？首先我们来看看我们要求的逆元是什么：对于 $kx \equiv 1 (\mod p), gcd(k, p) = 1$，我们要求的是 $x$. 接下来我们再看看 exgcd 求的是什么：对于 $ax+by=gcd(a, b)$，我们求得是 $x, y$ 的一组解。

其中式1： $kx \equiv 1 (\mod p)$ 可以转化为 $kx - py = gcd(k, p) = 1$，第二项的符号可以合到 $y$ 中去，然后令 $a=k, b=p$，就等于求解 $ax’+by’=gcd(a,b)=1$ 了，此时就可以用 exgcd 来求了，我们想要的逆元 $x$ 其实就是执行 exgcd 后 $x$ 的值。但此时的 $x$ 是在实数范围内的，可能有多组解，为了让我们的逆元在模 $p$ 的意义内唯一，我们可以对 $x$ 做如下变换：$x=(x\mod p+p)\mod p$，这就是我们要求的逆元了。

int x, y;
void exgcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1, y = 0;
        return;
    }
    exgcd(b, a % b, x, y);
    int tmp = x;
    x = y;
    y = tmp - (a / b) * y;
}
int inv(int k, int p) {
    exgcd(k, p, x, y);
    return ((x % p) + p) % p;
}

费马小定理

定理：假如 $a$ 是一个整数 $(a \in N)$，$p$ 是一个质数，那么 $a^p - a$ 是 $p$ 的倍数，可以表示为 $a^p - a\equiv 0 (\mod p)$，即 $a^p \equiv a (\mod p)$，从而 $a^{p-1} \equiv 1 (\mod p)$.

根据费马小定理公式 $a^{p-1} \equiv 1 (\mod p)$，有 $a \cdot a^{p-2} \equiv 1 (\mod p)$. 这里 $a^{p-2}$ 就是我们想求的逆元。$a^{p-2}$ 显然可以用快速幂来快速求得：

long long mod_pow(long long a, long long mod) {
    long long ans = 1, b = a;
    while (b) {
        if (b & 1)
            ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}
long long inv(long long num, long long mod) {
    return mod_pow(num, mod - 2, mod);
}

威尔逊定理

威尔逊定理是初等数论中用于判断一个自然数是否为素数的充要条件：

对于整数 $p$ ，当且仅当 $(p-1)! \equiv -1 (\mod p)$ 时，$p$ 为素数。

证明略去，有兴趣的话参见 https://www.jianshu.com/p/ad5bb5b8fa7d

唯一分解定理

唯一分解定理：一个大于 1 的正整数 $n$，能够被唯一分解为若干个质数幂次乘积的形式，即：$x=p_1^{a_1}\cdot p_2^{a_2} \cdot … \cdot p_n^{a_n}$，其中 $p_i$ 为质数。

根据唯一分解定理我们可以得到一些有用的推论：

一个整数 $n$ 的全体正因数之和为：$\Sigma(N)= (1+ p_1 + p_1 ^2 +… + p_1^{a_1}) (1+p_2 + p_2^2 +… + p_2^{a_2}) … (1+p_n + p_n^2 +… + p_n^{a_n})$

一个整数 $n$ 的正因子个数为：$f(n) = (1+a_1)(1+a_2)…(1+a_n)$

相关例题日后开文补吧。