数论进阶

记录一些结论作为备忘可以时常翻翻。

模意义下的数和运算

模相关简单运算

对于整数 $a, b$，满足 $b \gt 0$，那么存在唯一的整数 $q, r$，满足 $a = bq + r$，其中 $0 \leq r \lt b$。在这之中，我们称 $q$ 为商、$r$ 为余数。

余数使用 $a \mod b$ 或者 $a \% b$ 表示

一下是一些常见的有关模的运算：

• $(a + b) \mod M = (a \mod M + b \mod M) \mod M$
• $(a - b) \mod M = (a \mod M - b \mod M) \mod M$
• $(a \times b) \mod M = (a \mod M \times b \mod M) \mod M$

注意到除法并不适用，下文会引出乘法逆元解决模意义下的除法运算。

同余

如果两数 $x, y$ 除以 $b$ 的余数相等，那么称 $x, y$ 模 $b$ 同余，记作 $x \equiv y (\mod b)$。

以下性质显然：

• 反身性：$x \equiv x (\mod M)$
• 对称性：$x \equiv y (\mod M)$，则 $y \equiv x (\mod M)$
• 传递性：$x \equiv y (\mod M), y \equiv z (\mod M)$，则 $x \equiv z (\mod M)$

根据我们刚刚提到的模意义下的运算规律，还可以得到以下性质：

• 同加性：若 $x \equiv y (\mod M)$，则 $x + z \equiv y + z (\mod M)$
• 同乘性：若 $x \equiv y (\mod M)$，则 $x \times z \equiv y \times z (\mod M)$
• 同幂性：若 $x \equiv y (\mod M)$，则 $x^n \equiv y^n (\mod M)$

下面这条性质非常重要：

$$x \equiv y (\mod b) \Leftrightarrow b | (x - y)$$

同余方程和裴蜀定理

裴蜀定理

在 OI 中，形如 $ax + by = c$ 的二元一次不定方程只需要解决 $a, b, c$ 都是整数的情况。

对于整数 $a, b$，设他们的最大公约数 $\gcd(a, b) = d$，一定存在一组整数 $(x, y)$ 使得 $ax + by = d$。

对于整数 $a, b, c$，$ax + by = c$ 有整数解当且仅当 $\gcd(a, b) \lvert c$。

扩展欧几里得算法

欧几里得算法求 $a, b$ 最大值的过程：

1. 当 $b = 0$ 时，$a, b$ 的最大公约数就是 $a$
2. 求出 $b, a \mod b$ 的最大公约数，设为 $g_0$
3. 令 $g = g_0$，$g$ 就是 $a, b$ 的最大公约数

仿照欧几里得算法求解不定方程的过程：

1. 当 $b = 0$ 时，$ax + by = d$ 的解是 $x = \dfrac{d}{a}$，$\forall y$。
2. 求出 $bx + (a \mod b)y = d$ 的一组解，设为 $(x_0, y_0)$。
3. 令 $(x, y) = f((x_0, y_0))$，$(x, y)$ 就是 $a_x + b_y = d$ 的一组解。其中 $f((a, b))$ 指将 $(a, b)$ 这一对数进行变换。

变化如下：令 $(x, y) = (y_0, x_0 - \lfloor \dfrac{a}{b} \rfloor y_0)$。

可以发现，设 $a_x + b_y = d = k \times \gcd(a, b)$，那么每次迭代的得到的解都是在求解 $ax + by = \gcd(a, b)$ 时得到的解的 $k$ 倍，所以不管 $d$ 取多少，最后的迭代中取 $x = k, y = 0$ 是没有问题的。

C++ Template:

<template typename T>

T exgcd(T a, T b, T &x, T &y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }

    T d = exgcd(b, a % b, y, x);
    y -= a / b * x;

    return d;
}

乘法逆元

若 $ax \equiv 1 (\mod p)$，则称 $x$ 为 $a$ 在模 $p$ 意义下的乘法逆元，记为 $a^{-1} (\mod p)$

注意，在 $[0, p)$ 这一范围内，模 $p$ 的逆元（若存在）是唯一的。

求解乘法逆元的方法有两种：

扩欧求解乘法逆元

容易发现乘法逆元的定义式和 $\exists y, ax + py = 1$ 等价。这也就是一个关于 $a, p$ 的不定方程，使用扩欧解决，又裴蜀定理易得，存在 $a$ 在模 $p$ 意义下的逆元当且仅当 $\gcd(a, p) = 1, a \bot b$。

C++ Template:

<template typename T>

T exgcd(T a, T b, T &x, T &y) {
    // 参见上文
    ...
}

T inv(int a, int p) {
    int x, y;
    exgcd(a, p, x, y);
    return x;
}

费马小定理求解乘法逆元

费马小定理定义如下：

若 $\forall p \in \mathbb{P}$，且 $a$ 不是 $p$ 的倍数，则 $a^{p - 1} \equiv 1 (\mod p)$。

假设 $p$ 是质数，可知如果 $a$ 不是 $p$ 的倍数，有 $a \times a^{p - 2} = a^{p - 1} \equiv 1 (\mod p)$。所以 $a$ 在模 $p$ 意义下的乘法逆元就是 $a^{p - 2}$，可以使用快速幂解决。

C++ Template:

<template typename T>

T expow(T a, T b, const T p) {
    T res = 1;

    for (; b; b >>= 1) {
        if (b & 1)
            res = 1ll * res * a % p;

        a = 1ll * a * a % p;
    }

    return res;
}

T inv(T a, T p) {
    return expow(a, p - 2, p);
}

同余方程与中国剩余定理

中国剩余定理

一般而言，中国剩余定理用来解决这样的一类同余方程组：

$$\begin{cases} x \equiv a_1 (\mod m_1) \\ x \equiv a_2 (\mod m_2) \\ \vdots \\ x \equiv a_n (\mod m_n) \end{cases}$$

其中，$m_1, m_2, \dots, m_n$ 两两互质，则对于任意整数 $a_1, a_2, \dots, a_n$，上面这个方程组有解。

解决方法如下：

1. 设 $M = \prod^{n}_{i = 1} m_i$
2. 设 $M_i = \dfrac{M}{m_i}$
3. 设 $t_i = M^{-1}_i$ 为 $M_i \mod m_i$ 的逆元（因为 $M_i$ 和 $m_i$ 互质，所以逆元一定存在）
4. $x$ 的通解即为 $x = \sum_{i = 1}^n a_i t_i M_i + kM, k \in \mathbb{Z}$

扩展中国剩余定理

问题格式同上，但是没有了 $m_1, m_2, \dots, m_n$ 两两互质的条件。

引入定理：如果有特解 $x^*$，那么对于

$$\begin{cases} x \equiv r_1 (\mod m_1) \\ x \equiv r_2 (\mod m_2) \end{cases}$$

的通解是 $x^* + k \times \text{lcm}(m_1, m_2)$，也就是 $x \equiv x^* (\mod \text{lcm}(m_1, m_2))$

因此，处理 exCRT 的过程就是不断从方程组内取出两个方程，尝试进行合并然后再压入方程组内，如果无解退出，否则最后方程组内剩下的唯一一个方程就是解系。

线性筛和积性函数

暂待加工。