最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

数论笔记-同余

来源：博客园
目录
  • 同余
    • 带余数除法
      • 带余数除法的定义与基本性质
      • 模运算加速算法
        • 龟速乘
        • 快速幂
        • 矩阵快速幂
    • 同余的定义与基本性质
    • 同余类与剩余系的定义与基本性质
    • 欧拉函数
      • 欧拉函数的定义与基本性质
      • 欧拉函数的求法
        • 试除法
        • 线性筛求欧拉函数
      • 欧拉函数的其他性质
    • 同余重要定理
      • 费马小定理
      • 欧拉定理
      • 威尔逊定理
    • 二元一次不定方程
      • 二元一次不定方程的定义与基本性质
      • 解二元一次不定方程
        • 扩展欧几里得算法
      • 类欧几里得算法
    • 乘法逆元
      • 乘法逆元的定义与基本性质
      • 乘法逆元的求法
        • 费马小定理法
        • 扩展欧几里得法
        • 线性求乘法逆元
        • 线性求阶乘逆元
    • 一元一次同余方程
      • 一元一次同余方程的定义与基本性质
      • 解一元一次同余方程
        • 扩展欧几里得算法
      • 解一元一次同余方程组
        • 中国剩余定理
        • 扩展中国剩余定理

同余

带余数除法

带余数除法的定义与基本性质

定义对于整数 \(a,b\) ，一定存在整数 \(q,r\) 满足 \(a = bq + r\) ，其中 \(r\) 与 \(a\) 同号且 \(|r| \in [0,b)\) ，称 \(q\) 为 \(a\) 除以 \(b\) 的商， \(r\) 为 \(a\) 除以 \(b\) 的余数。

通常我们定义 \(b\) 是正整数，但为了和c++语法统一，因此修改了定义。

模运算的定义\(a \bmod b\) 表示 \(a\) 除以 \(b\) 的余数 \(r\) ，符号和 \(a\) 一致，运算优先级同乘除。


(资料图片仅供参考)

模 \(m\) 加法\((a+b) \bmod m\) 。

模 \(m\) 减法\((a-b) \bmod m\) 。

模 \(m\) 乘法\(ab \bmod m\) 。

性质1\(a \bmod b = a - b\times \lfloor \frac{a}{b}\rfloor\) 。

性质2

\[\begin{aligned}a \bmod m \pm b \bmod m &= (a\pm b) \bmod m\\(a \bmod m) \cdot (b \bmod m) &= ab \bmod m\\(a \bmod m)^k &= a^k \bmod m\end{aligned}\]

性质3\(a \bmod n = a\bmod m = x\) 且 \(\gcd(n,m) = 1\) ，则 \(a \bmod nm = x\)

模运算加速算法

龟速乘

用于可能爆 long long数字的乘法取余。

不过一般可以用 __int128替代了。

时间复杂度 \(O(\log b)\)

空间复杂度 \(O(1)\)

const int P = 1e9 + 7;ll qmul(ll a, ll b) {    ll ans = 0;    while (b) {        if (b & 1) ans = (ans + a) % P;        b >>= 1;        a = (a << 1) % P;    }    return ans;}

快速幂

幂取余，\(a\) 越大速度越慢。

时间复杂度 \(O(\log k)\)

空间复杂度 \(O(1)\)

const int P = 1e9 + 7;ll qpow(ll a, ll k) {    ll ans = 1;    while (k) {        if (k & 1) ans = ans * a % P;        k >>= 1;        a = a * a % P;    }    return ans;}

矩阵快速幂

矩阵幂取余。

时间复杂度 \(O(n^3 \log k)\)

空间复杂度 \(O(1)\)

const int P = 1e9 + 7;struct Matrix {    int n, m;//不能const，快速幂要复制    vector> mat;    explicit Matrix(int _n):n(_n), m(_n), mat(_n + 1, vector(_n + 1)) {        for (int i = 1;i <= n;i++)            for (int j = 1;j <= m;j++)                mat[i][j] = i == j;    }//初始化n阶单位矩阵，explicit防止误用类型转换    Matrix(int _n, int _m):n(_n), m(_m), mat(_n + 1, vector(_m + 1)) {}//初始化nxm零矩阵    friend Matrix operator*(const Matrix &A, const Matrix &B) {        Matrix ans(A.n, B.m);        if (A.m != B.n) return ans;        for (int i = 1;i <= A.n;i++)            for (int j = 1;j <= B.m;j++)                for (int k = 1;k <= A.m;k++) //a.m == b.n                    ans.mat[i][j] = (ans.mat[i][j] + A.mat[i][k] * B.mat[k][j]) % P;        return ans;    }//矩阵乘法取余    friend Matrix operator^(Matrix A, ll k) {        Matrix ans(A.n);//A必须是方阵        while (k) {            if (k & 1) ans = ans * A;            k >>= 1;            A = A * A;        }        return ans;    }//快速幂取余    void output() const {        for (int i = 1; i <= n; i++) {            for (int j = 1; j <= m; j++)                cout << mat[i][j] << " ";            cout << "\n";        }        cout << "\n";    }//输出检测};

同余的定义与基本性质

定义若整数 \(a,b\) 模 \(m\) 相等，则称 \(a,b\) 模 \(m\) 同余，记作 \(a \equiv b \pmod m\) 。

以下讨论均为整数。

性质1（自反性）\(a \equiv a \pmod m\) 。

性质2（对称性）\(a\equiv b \pmod m \iff b \equiv a \pmod m\) 。

性质3（传递性）\(a \equiv b \pmod m,b \equiv c \pmod m \Rightarrow a \equiv c \pmod m\) 。

性质4（同加性）

\[\begin{aligned}a \equiv b \pmod m &\iff a \pm c \equiv b \pm c \pmod m\\a \equiv b \pmod m,c \equiv d \pmod m &\iff a \pm c \equiv b \pm d \pmod m\end{aligned}\]

性质5（同乘性）

\[\begin{aligned}a \equiv b \pmod m &\Rightarrow ac \equiv bc \pmod m\\a \equiv b \pmod m,c \equiv d \pmod m &\Rightarrow ac \equiv bd \pmod m\end{aligned}\]

性质6（同幂性）\(a \equiv b \pmod m \Rightarrow a^k \equiv b^k \pmod m\) ，其中 \(k \geq 0\)。

性质7（特殊同除性）\(a \equiv b \pmod m \Rightarrow \dfrac{a}{d} \equiv \dfrac{b}{d} \pmod {\dfrac{m}{\gcd(m,d)}}\) ，其中 \(d\) 满足 \(d \mid a,d \mid b\) 。

性质8\(a \equiv b \pmod m,m" \mid m \Rightarrow a \equiv b \pmod {m"}\) 。

性质9\(a \equiv b \pmod {m_i}(i = 1,2,\cdots,n) \iff a \equiv b \pmod M ,M = \text{lcm}(m_1,m_2,\cdots,m_n)\) 。

性质10\(a \equiv b \pmod m \Rightarrow \gcd(a,m) = \gcd(b,m)\) 。

同余类与剩余系的定义与基本性质

同余类的定义对于 \(a \in [0,m-1]\) ，集合 \(\{a + km\},k \in \Z\) 的所有数模 \(m\) 同余 \(a\) ，称这个集合为模 \(m\) 的一个同余类 \(\overline a\) 。

完全剩余系的定义模 \(m\) 的同余类有 \(m\) 个，分别为 \(\overline 0,\overline 1,\cdots ,\overline {m-1}\) ，它们构成了 \(m\) 的完全剩余系。

既约剩余系的定义模 \(m\) 的同余类有 \(\varphi(m)\) 个的代表元与 \(m\) 互质，它们构成了 \(m\) 的既约剩余系（简化剩余系）。

\(\varphi(m)\) 为欧拉函数，下一节会讲到。

性质1设 \(S\) 是模 \(m\) 的一个完全剩余系，若 \(\gcd(k,m) = 1\) ，则 \(S" = \{x" \mid x" = kx+b,x\in S \}\) 也是模 \(m\) 的一个完全剩余系。

性质2设模 \(m_1\) 的完全剩余系为 \(S_1\) ，模 \(m_2\) 的完全剩余系为 \(S_2\) ，且 \(\gcd(m_1,m_2) = 1\) ，则模 \(m = m_1m_2\) 的完全剩余系为 \(S = \{x\mid x = m_2x_1 + m_1x_2,x_1 \in S_1,x_2 \in S_2\}\) 。

性质3设 \(S\) 是模 \(m\) 的一个既约剩余系，若 \(\gcd(k,m) = 1\) ，则 \(S" = \{x" \mid x" = kx,x\in S \}\) 也是模 \(m\) 的一个既约剩余系。

性质4设模 \(m_1\) 的既约剩余系为 \(S_1\) ，模 \(m_2\) 的既约剩余系为 \(S_2\) ，且 \(\gcd(m_1,m_2) = 1\) ，则模 \(m = m_1m_2\) 的既约剩余系为 \(S = \{x\mid x = m_2x_1 + m_1x_2,x_1 \in S_1,x_2 \in S_2\}\) 。

推论1（性质4的推论）\(\gcd(m_1,m_2) = 1 \Rightarrow \varphi(m_1m_2) = \varphi(m_1)\varphi(m_2)\) ，即欧拉函数是积性函数。

性质1的证明：

假设存在 \(kx_i + b \equiv kx_j + b \pmod m\) ，则 \(kx_i \equiv kx_j \pmod m\) 。因为 \(\gcd(k,m) = 1\) ，所以 \(x_i \equiv x_j \pmod m\) ，\(x_i,x_j\) 属于一个同余类，矛盾。综上，得证。

性质2的证明：

假设存在 \(m_2x_1 + m_1x_2 \equiv m_2x_1"+m_1x_2" \pmod m\) ，那么 \(m_2(x_1-x_1") \equiv m_1(x_2"-x_2) \pmod m\) 。因为 \(m_1 \mid m\) ，所以 \(m_2(x_1-x_1") \equiv m_1(x_2"-x_2) \equiv 0 \pmod {m_1}\) ，又 \(\gcd(m_1,m_2) = 1\) ，所以 \(x_1-x_1" \equiv 0 \pmod {m_1}\) ，矛盾。综上，得证。

性质3的证明：

根据性质1证明，类似可得 \(S"\) 一定是 \(m\) 的一个剩余系，且有 \(\varphi(m)\) 个元素，接下来只需证明任意元素都与 \(m\) 互质。

任意 \(x \in S\) ，有 \(\gcd(x,m) = 1\) ，又 \(\gcd(k,m) = 1\) ，所以 \(\gcd(kx,m) = 1\) ，所以 \(S"\) 是模 \(m\) 的既约剩余系。

性质4的证明：

根据性质2证明，类似可得 \(S\) 一定是模 \(m\) 的一个剩余系，且有 \(\varphi(m_1)\cdot\varphi(m_2)\) 个元素，但我们并不知道 \(\varphi(m_1)\cdot\varphi(m_2) = \varphi(m_1m_2)\) ，因此我们证明 \(S\) 的元素都与 \(m\) 互质只能说明 \(S\) 是模 \(m\) 的既约剩余系的一个子集，我们还需要证明模 \(m\) 的既约剩余系是 \(S\) 的一个子集。

若 \(\gcd(x_1,m_1) = \gcd(x_2,m_2) = 1\) ，又 \(\gcd(m_1,m_2) = 1\) ，因此 \(\gcd(m_2x_1,m_1) = \gcd(m_1x_2,m_2) = 1\) ，所以 \(\gcd(m_2x_1 + m_1x_2,m_1) = \gcd(m_1x_2+m_2x_1,m_2) = 1\) ，于是 \(\gcd(m_1x_2+m_2x_1,m_1m_2) = 1\) ，即 \(S\) 是模 \(m\) 的既约剩余系的子集。

因为 \(\gcd(m_1,m_2) = 1\) ，因此 \(m_2x_1+m_1x_2\) 可以表达所有整数。那么令模 \(m\) 的既约剩余系的元素为 \(m_2x_1+m_1x_2\) ，则 \(\gcd(m_2x_1+m_1x_2,m_1m_2) = 1\) ，因此 \(\gcd(m_2x_1+m_1x_2,m_1) = \gcd(m_2x_1+m_1x_2,m_2) = 1\) ，所以 \(\gcd(m_2x_1,m_1) = \gcd(m_1x_2,m_2) = 1\) ，又 \(\gcd(m_1,m_2) = 1\) ，于是 \(\gcd(x_1,m_1) = \gcd(x_2,m_2) = 1\) ，即模 \(m\) 的既约剩余系是 \(S\) 的子集。

综上 \(S\) 就是模 \(m\) 的既约剩余系。

推论1的证明：

由性质4，可得 \(S\) 的元素个数是 \(\varphi(m_1)\varphi(m_2)\) ，而模 \(m\) 的既约剩余系的元素个数是 \(\varphi(m_1m_2)\) 。因此，当 \(\gcd(m_1,m_2) = 1\) ， \(\varphi(m_1m_2) = \varphi(m_1)\varphi(m_2)\) ，即欧拉函数是积性函数。

欧拉函数

欧拉函数的定义与基本性质

定义\([1,n]\) 中与 \(n\) 互质的个数记作 \(\varphi(n)\) 。

性质1\(\varphi(p) = p-1\) ，其中 \(p\) 为素数。

性质2\(\varphi(p^k) = p^k - p^{k-1}\) ，其中 \(k\in \Z^+\) ， \(p\) 为素数。

性质3欧拉函数是积性函数，即 \(\gcd(a,b) = 1 \Rightarrow \varphi(ab) = \varphi(a)\cdot \varphi(b)\) 。

性质4int范围内欧拉函数的最大值为 \(1600\) 。

由性质1、2、3可以得到引理：

引理1（欧拉函数的展开式）

\[\begin{aligned}\varphi(n) &= \varphi\bigg( \prod_{i = 1}^k p_i^{c_i} \bigg)\\ &= \prod_{i = 1}^k\varphi (p_i^{c_i}) \\ &= \prod_{i = 1}^k (p_i^{c_i}-p_i^{c_i-1})\\ &= n\prod_{p\mid n}\bigg(1-\frac{1}{p}\bigg)\end{aligned}\]

其中 \(p\) 是素数。

欧拉函数的求法

试除法

线性筛求欧拉函数

欧拉函数的其他性质

同余重要定理

费马小定理

欧拉定理

威尔逊定理

二元一次不定方程

二元一次不定方程的定义与基本性质

裴蜀定理

解二元一次不定方程

扩展欧几里得算法

类欧几里得算法

乘法逆元

乘法逆元的定义与基本性质

乘法逆元的求法

费马小定理法

扩展欧几里得法

线性求乘法逆元

线性求阶乘逆元

一元一次同余方程

一元一次同余方程的定义与基本性质

解一元一次同余方程

扩展欧几里得算法

解一元一次同余方程组

中国剩余定理

扩展中国剩余定理

关键词： 二元一次 一次同余方程 欧几里得算法