数数论

同余

字数统计: 2.2k字   |   阅读时长: 10分
, ,

摘要: 本文介绍同余的算法原理和代码模板、以及几道相关题目

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

各位好，本文详细研究同余以及相关的定理。主要内容如下：

  • 同余的定义
  • 同余类与剩余系
  • 费马小定理
  • 欧拉定理
  • 欧拉定理推论
  • 扩展欧几里得算法
  • 乘法逆元
    • 求逆元的算法
  • 线性同余方程
    • 中国剩余定理
  • 高次同余方程

同余的定义

整数 a 和整数 b 除以正整数 m 的余数相同，称 a, b 模 m 同余，记为 $a \equiv b \mod m$。

同余类与剩余系

对于 $\forall a \in [0, m-1]$，集合 $\{a+km\}(k \in \mathbb{Z})$ 的所有数模 m 同余。余数都是 a。该集合称为一个模 m 的同余类。记为 $\bar{a}$。

模 m 的同余类一共有 m 个。构成 m 的完全剩余系。

1~m 中与 m 互质的数代表的同余类共有 $\phi(m)$ 个。构成 m 的简化剩余系。例如 10 的简化剩余系为 $\{\bar{1}, \bar{3}, \bar{7}, \bar{9}\}$。

费马小定理

若 p 为质数，则对 $\forall a$ 有 $a^{p} \equiv a (\mod p)$。

欧拉定理

若 a, n 为正整数且 a, n 互质，则 $a^{\phi(n)} \equiv 1 \mod n$。

欧拉定理推论

若 a, n 为正整数且 a, n 互质，则 $\forall b \in \mathbb{N}^{*}$ 有 $a^{b} \equiv a^{b \mod \phi(n)} \mod n$。

扩展欧拉定理

处理 a, n 不一定互质的情况。

若 a, n 为正整数，则

应用：降幂。例如题目 372. 超级次方，题解参考 组合数学4-容斥原理,鸽巢原理。

扩展欧几里得算法

扩展欧几里得算法是欧几里得算法（又叫辗转相除法）的扩展，这里我们先看裴蜀定理，裴蜀定理的证明过程就是扩展欧几里得算法。

Bezout定理(裴蜀定理)

对于任意整数 a, b，存在一对整数 x, y, 使得 $ax + by = gcd(a, b)$

扩展裴蜀定理

$a_{1}x_{1} + a_{2}x_{2} + … + a_{n}x_{n} = d$ 有整数解 $gcd(a_{1}, a_{2}, …, a_{n})$

例题: 1250. 检查「好数组」

给你一个正整数数组 nums，你需要从中任选一些子集，然后将子集中每一个数乘以一个 任意整数，并求出他们的和。

假如该和结果为 1，那么原数组就是一个「好数组」，则返回 True；否则请返回 False。

提示：

1
2
1 <= nums.length <= 1e5
1 <= nums[i] <= 1e9

示例 1：
输入：nums = [12,5,7,23]
输出：true
解释：挑选数字 5 和 7。
53 + 7(-2) = 1

示例 2：
输入：nums = [29,6,10]
输出：true
解释：挑选数字 29, 6 和 10。
291 + 6(-3) + 10*(-1) = 1

示例 3：
输入：nums = [3,6]
输出：false

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    bool isGoodArray(vector<int>& nums) {
        if(nums.empty()) return false;
        int n = nums.size();
        if(n == 1) return abs(nums[0]) == 1;
        int all_gcd = gcd<int>(abs(nums[0]), abs(nums[1]));
        for(int i = 2; i < n;++i)
            all_gcd = gcd<int>(all_gcd, abs(nums[i]));
        return all_gcd == 1;
    }
};

扩展欧几里得算法

裴蜀定理的证明过程就是扩展欧几里得算法。

除了计算 a、b 两个整数的最大公约数，此算法还能找到整数 x、y（其中一个很可能是负数）使得 ax + by = gcd(a,b)。

代码模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
ll exgcd(ll a, ll b, ll& x, ll& y)
{
    // 求出 ax + by = gcd(a, b) 的一组特接并返回 a,b 的最大公约数 d。
    if(b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    ll d = exgcd(b, a % b, x, y);
    int z = x;
    x = y;
    y = z - y * (a / b);
    return d;
}

乘法逆元

若 b, m 互质，且 $b | a$，则 $\exists x$ 使得 $a / b \equiv ax \mod m$，称 x 为 b 模 m 的乘法逆元，记为 $b^{-1} \mod m$

$a/b \equiv ab^{-1} \equiv a/b \times b \times b^{-1} \mod m \Rightarrow b \times b^{-1} \equiv 1 \mod m$

p 为质数时，$b^{p-2}$ 为 $b$ 的乘法逆元。

若只保证了 b, m 互质，乘法逆元可以通过求解线性同余方程 $b \times x \equiv 1 \mod m$ 得到。

应用：当要求 $a / b \mod p$ 时(b, p 互质)，可以先求出 a, b 各自模 p 的值，再计算 $a \times b^{-1} \mod p$。

算法1. 扩展欧几里得法，只要逆元存在即可求

用扩展欧几里得算法解 $bx + py = 1$ 得到 b 的逆元，时间复杂度为 $O(\log N)$，相当于快速幂。

1
2
3
4
5
6
7
8
9
10
11
// 求 b 模 p 的乘法逆元 (b 与 p 互质)
ll inv(ll b, ll p)
{
    // 解方程 bx 与 1 模 p 同余
    // 扩展欧几里得求 bx0 + py0 = 1
    ll x0 = 0, y0 = 0;
    ll d = exgcd(b, p, x0, y0);
    if(d != 1) // b 和 p 不互质的情况不不存在逆元
        return -1;
    return (x0 % p + p) % p;
}

算法2. 费马小定理

若 p 为质数，则对 $\forall a$ 有 $a^{p} \equiv a (\mod p)$，于是 $a^{p−2}$ 就是 $a$ 在 $\mod p$ 意义下的逆元。

费马小定理一般形式也就是欧拉定理: 当 p 不为质数，但 a, p 互质，则 $a^{\phi(p)} \equiv 1 \mod p$。

于是 $a^{\phi(p)-1}$ 就是 $a$ 在 $\mod p$ 意义下的逆元。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 模下快速幂
int quickpower2(int a, int n, int m) // 处理不了n是负数
{
    int ans = 1;
    while(n)
    {
        if(n & 1) ans = ((ll)ans * a) % m;
        a = (ll)a * a % m;
        n >>= 1;
    }
    return ans;
}

ll inv(ll b, ll p)
{
    return quickpower2(b, p - 2, p);
}

算法3：递推求逆元

$i$ 为待求的逆元，即求 $i^{-1}$ 在 $\mod p$ 意义下的值。

因此 inv[i] = -(p/i)*inv[i%p]，边界 inv[1] = 1。这种递推法求逆元经常用于预处理得到 inv 数组，此后多次调用。

1
2
3
4
5
6
7
8
9
10
vector<int> get_inv(ll p)
{
    vector<int> vec(p);
    vec[1] = 1;
    for(int i = 2; i < p; ++i)
        vec[i] = p - (p / i) * vec[p % i] % p;
    return vec;
}

vector<int> inv = get_inv(p);

预处理好 inv 数组之后，调用 inv[b] 前先将 b 对 p 取模。时间和空间复杂度均为 $O(p)$ 适用于 p 为不大的素数且需要多次调用，例如卢卡斯定理。

算法4：递归求逆元

需要 p 为素数。

1
2
3
4
5
6
ll inv(ll b, ll p)
{
    if(b == 1)
        return 1;
    return (p - p / b) * inv(p % b, p) % p;
}

线性同余方程

给定整数 a, b, m, 求一个整数 x 满足 $a \times x \equiv b \mod m$，或确定该方程无解。x 为一次时称为线性同余方程。

$a \times x \equiv b \mod m \Leftrightarrow ax + my = b$

由裴蜀定理，$a \times x \equiv b \mod m$ 有解 $\Leftrightarrow ax + my = b$ 有解 $\Leftrightarrow gcd(a, m) | b$

当确定线性同余方程 $a \times x \equiv b \mod m$ 有解后，用扩展欧几里得算法求出 $x_{0}, y_{0}$ 使得 $ax_{0} + my_{0} = gcd(a, m)$，然后 $x = x_{0} \times b / gcd(a, m)$ 为一个解。通解: 所有模 $m/gcd(a, m)$ 与 x 同余的整数。

应用(判断丢番图方程有无解)：力扣365-水壶问题,BFS,裴蜀定理。

中国剩余定理

m 和 n 为互质正整数，对任意非负整数 a, b($a < m, b < n$)，必存在正整数 x，使得下式成立：

证明用到鸽巢原理，参考 组合数学4-容斥原理,鸽巢原理。

中国剩余定理的推广

$m_{1}, …, m_{k}$ 两两互质：$gcd(m_{i}, m_{j}) = 1, i \neq j$

则以下同余式有解

解为 $x = \sum\limits_{i=1}\limits^{n}a_{i}M_{i}t_{i}$，其中 $M_{i} = \frac{m}{m_{i}}, m = \prod\limits_{i=1}\limits^{k}$，$t_{i}$ 是线性同余方程 $M_{i}t_{i} \equiv 1 (\mod m_{i})$ 的一个解。

中国剩余定理的推广给出模数两两互质的线性同余方程组的一个特解。通解为 $x + km (k \in \mathbb{Z})$

若要求最小非负整数解，通过取模让 x 落在 0 ~ m - 1 分为内即可。

高次同余方程

第一类 $a^{x} \equiv b (\mod p)$

  • b, p 互质
  • Baby Step Gaint Step 算法

第二类 $x^{a} \equiv b (\mod p)$

很难，涉及到原根等概念。

Share