数论笔记-同余

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

同余

带余数除法

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

定义 对于整数 \(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 \left\lfloor \dfrac{a}{b} \right\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<vector<ll>> mat;

    explicit Matrix(int _n):n(_n), m(_n), mat(_n + 1, vector<ll>(_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<ll>(_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)\)

性质4(欧拉函数的展开式) \(\displaystyle \varphi(n) = n\prod_{p\mid n}\left(1-\frac{1}{p}\right)\)

性质5 \(p \mid n,p^2 \not \mid n \Rightarrow \varphi(n) = (p-1)\varphi\left(\dfrac{n}{p}\right)\) ,其中 \(p\) 为素数。

性质6 \(p^2 \mid n \Rightarrow \varphi(n) = p\varphi\left(\dfrac{n}{p}\right)\) ,其中 \(p\) 为素数。

性质4的证明:

\[\begin{aligned} \varphi(n) &= \varphi\left( \prod_{i = 1}^k p_i^{c_i} \right)\\ &= \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}\left(1-\frac{1}{p}\right) \end{aligned} \]

其中 \(p\) 是素数。

由此还能得出性质5和6。

欧拉函数的求法

试除法

利用试除法的分解质因子,通过性质4累乘即可,适用于只求单个欧拉函数的值。

可以提前 \(O(n)\) 预处理素数,时间复杂度 \(O\left(\dfrac{\sqrt n}{\ln n}\right)\) ,空间复杂度 \(O(n)\)

时间复杂度 \(O(\sqrt n)\)

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

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

线性筛求欧拉函数

对于素数 \(p\) ,直接令 \(\varphi(p) = p-1\)

对于合数 \(n\) ,因为只会在 \(i = \dfrac{n}{p}\) 时被最小质因子 \(p\) 筛一次,因此我们可以递推,但需要分类讨论:

  1. \(p\)\(i\) 的最小质因子小,满足性质5,因此 \(\varphi(n) = \varphi(p) \cdot \varphi(i) = (p-1)\varphi(i)\)
  2. \(p\)\(i\) 的最小质因子,满足性质6, \(\varphi(n) = p\varphi(i)\)

时间复杂度 \(O(n)\)

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

const int N = 1e7 + 7;
bool vis[N];
vector<int> prime;
int phi[N];
void get_euler(int n) {
    phi[1] = 1;
    for (int i = 2;i <= n;i++) {
        if (!vis[i]) {
            prime.push_back(i);
            phi[i] = i - 1;
        }
        for (int j = 0;j < prime.size() && i * prime[j] <= n;j++) {
            vis[i * prime[j]] = 1;
            if (!(i % prime[j])) {
                phi[i * prime[j]] = prime[j] * phi[i];
                break;
            }
            phi[i * prime[j]] = (prime[j] - 1) * phi[i];
        }
    }
}

欧拉函数的其他性质

性质1\(n \geq 3\) 时,\(\varphi(n)\) 为偶数。

性质2 \(f(n) = \displaystyle \sum_{i = 1}^n [\gcd(i,k) = 1] = \left\lfloor\frac{n}{k}\right\rfloor \varphi(n) + f(n \bmod k)\)

性质3 \(\displaystyle \sum_{i = 1}^n i[\gcd(i,n) = 1] = \frac{n\varphi(n) + [n = 1]}{2}\)

性质4 \(\displaystyle \sum_{d\mid n} \varphi(d) = n\)

性质5 \(\varphi(ab) = \dfrac{\varphi(a) \cdot \varphi(b) \cdot \gcd(a,b)}{\varphi(\gcd(a,b))}\)

性质6 \(d^2 \mid n \Rightarrow \varphi(n) = d\varphi\left(\dfrac{n}{d}\right)\)

推论1(性质5和6的推论)\(n = abd^k,k\geq 2\)\(\gcd(a,b)=1\) ,则 \(\varphi(n) = d^{k-2}\varphi(abd^2) = d^{k-2} \dfrac{\varphi(ad) \cdot \varphi(bd) \cdot d}{\varphi(d)}\)

性质1的证明:

对于 \(n \geq 3\) ,当 \(m < n\) ,若 \(\gcd(m,n)=1\) ,则 \(\gcd(n-m,n) = 1\) ,同时 \(m \neq n-m\)

因此每一个与 \(n\) 互质的数 \(m\) 都对应一个 \(n-m\) 也与 \(n\) 互质,所以 \(\varphi(n)\) 为偶数。

性质2的证明:

\(f(n)\) 等同于 \([1,n]\) 中与 \(k\) 互质的数的个数。

我们把 \([1,n]\)\(k\) 个数分一段,能分完整的 \(\left\lfloor\frac{n}{k}\right\rfloor\) 段,以及 \(n \bmod k\) 个多出来的数。

根据 \(\gcd(a,b) = \gcd(a \bmod b,b)\) ,因此 \([1+mk,k+mk]\) 中与 \(k\) 互质的数等于 \([1,k]\) 中与 \(k\) 互质的数,因此完整的 \(\left\lfloor\frac{n}{k}\right\rfloor\) 段中,共有 \(\left\lfloor\frac{n}{k}\right\rfloor \varphi(k)\) 个与 \(k\) 互质的数。而 \([1+\left\lfloor\frac{n}{k}\right\rfloor k,n]\) 中与 \(k\) 互质的数等于 \([1,n \bmod k]\) 中与 \(k\) 互质的数,即 \(f(n \bmod k)\)

综上 \(f(n) = \displaystyle \sum_{i = 1}^n [\gcd(i,k) = 1] = \left\lfloor\frac{n}{k}\right\rfloor \varphi(n) + f(n \bmod k)\)

性质3的证明:

左式等同于 \([1,n]\) 中与 \(n\) 互质的数的和。

\(n \geq 3\) 时,根据性质 \(1\) ,互质的数一定形如 \(m,n-m\) 成对出现,因此总和的平均值为 \(\dfrac{n}{2}\) ,因此总和为 \(n\dfrac{\varphi(n)}{2}\)

\(n = 2\) 时,上式也成立。

\(n=1\) 时,上式结果为 \(\dfrac{1}{2}\) ,因此增加修正 \(\dfrac{[n=1]}{2}\)

综上, \(\displaystyle \sum_{i = 1}^n i[\gcd(i,n) = 1] = \frac{n\varphi(n) + [n = 1]}{2}\)

性质4的证明:

\(\displaystyle f(x) = \sum_{i=1}^n [\gcd(i,n) = x]\) ,则 \(\displaystyle \sum_{i=1}^n f(i) = n\) ,这是因为每个数的 \(\gcd\) 唯一,遍历一遍 \(\gcd\) 能覆盖 \(n\)

\(\gcd(i,n) = d \iff \gcd\left( \dfrac{i}{d},\dfrac{n}{d} \right) = 1\) ,所以当 \(x \mid n\) 时, \(\displaystyle f(x) = \sum_{i=1}^{\frac{n}{x}} [\gcd\left(i,\frac{n}{x} \right) = 1] = \varphi\left(\frac{n}{x}\right)\) ;当 \(x \not \mid n\) 时, \(f(x) = 0\)

综上 \(\displaystyle \sum_{d \mid n} \varphi(d) = \sum_{d \mid n} \varphi\left(\frac{n}{d}\right) = \sum_{d \mid n} f(d) = \displaystyle \sum_{i=1}^n f(i) =n\)

性质5的证明:

根据基本性质5可得

\[\begin{aligned} \varphi(ab) &= ab\prod_{p\mid ab}\left(1-\frac{1}{p}\right)\\ &= \frac{\displaystyle a\prod_{p\mid a}\left(1-\frac{1}{p}\right) \cdot b\prod_{p\mid b}\left(1-\frac{1}{p}\right)}{\displaystyle\prod_{p\mid a \cap p\mid b}\left(1-\frac{1}{p}\right)}\\ &= \frac{\varphi(a) \cdot \varphi(b)\cdot\gcd(a,b)}{\displaystyle \gcd(a,b) \prod_{p\mid \gcd(a,b)}\left(1-\frac{1}{p}\right)}\\ &= \dfrac{\varphi(a) \cdot \varphi(b) \cdot \gcd(a,b)}{\varphi(\gcd(a,b))} \end{aligned} \]

性质6的证明:

因为 \(d^2 \mid n\) ,所以 \(n\)\(\dfrac{n}{d}\) 的质因子相同,因此 \(\displaystyle \varphi(n) = n\prod_{p\mid n}\left(1-\frac{1}{p}\right) = d \cdot \frac{n}{d} \prod_{p\mid \frac{n}{d}}\left(1-\frac{1}{p}\right) = d\varphi\left(\dfrac{n}{d}\right)\)

同余重要定理

费马小定理

定理1(费马小定理)\(p\) 为质数且整数 \(a\) 不是 \(p\) 的倍数,则 \(a^{p-1} \equiv 1 \pmod p\)

定理2(费马大定理) 若整数 \(n \geq 3\) ,则 \(x^n+y^n=z^n\) 无正整数解。

推论1(定理1的推论,费马降幂)\(p\) 为质数且整数 \(a\) 不是 \(p\) 的倍数,则 \(a^n \equiv a^{n \mod (p-1)} \pmod p\)

定理1的证明:

由欧拉定理可得, \(\varphi(p) = p-1\) ,且 \(\gcd(a,p)=1\) ,因此 \(a^{p-1} \equiv 1 \pmod p\)

欧拉定理见下一节。

定理2的证明:

我有一个绝妙的证明方法,但这里地方太小了我写不下qwq。

欧拉定理

定理1(欧拉定理) 若正整数 \(a,m\) 互质,则 \(a^{\varphi(m)} \equiv 1 \pmod m\)

定理2(拓展欧拉定理)

\[a^b \equiv \left\{ \begin{array}{l} a^{b \mod \varphi(m)} &,\gcd(a,m) = 1\\ a^b &,b < \varphi(m) \text{ 且 }\gcd(a,m) \neq 1\\ a^{b \mod \varphi(m) + \varphi(m)} &,b \geq \varphi(m) \text{ 且 }\gcd(a,m) \neq 1\\ \end{array} \right. \pmod m \]

推论1(定理1的推论) \(\exist x \in \Z^+ ,a^x \bmod m = 1 \iff \gcd(a,m) = 1\)

定理1的证明:

\(\{x_1,x_2,\cdots,x_{\varphi(m)}\}\) 是一个模 \(m\) 的既约剩余系。

根据同余类与剩余系基本性质3,因为 \(\gcd(a,m) = 1\) ,所以 \(\{ax_1,ax_2,\cdots,ax_{\varphi(m)}\}\) 也是模 \(m\) 的一个既约剩余系。因此, \(x_1x_2\cdots x_{\varphi(m)} \equiv a^{\varphi(m)}x_1x_2\cdots x_{\varphi(m)} \pmod m\)

\(\gcd(x_1,m) = \cdots = \gcd(x_{\varphi(m)},m) = 1\) ,所以 \(\gcd(x_1x_2 \cdots x_{\varphi(m)},m) = 1\) ,于是 \(a^{\varphi(m)} \equiv 1 \pmod m\)

定理2的证明:

见此链接

推论1的证明:

从左到右,由条件 \(\exist x \in \N^+,\gcd(a^x,m) = \gcd(a^x \bmod m,m) =\gcd(1,m) = 1\) ,所以 \(\gcd(a^x,m) = \gcd(a,m) = 1\)

从右到左,根据欧拉定理显然。

威尔逊定理

定理1(威尔逊定理)\(p\) 为素数,则满足 \((p-1)! \equiv -1 \pmod p\)

定理2(定理1的逆命题)\(p\) 满足 \((p-1)! \equiv -1 \pmod p\) ,则 \(p\) 为素数。

推论1(定理1和2的推论) \(p\) 为素数,当且仅当 \((p-1)! \equiv -1 \pmod p\)

二元一次不定方程

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

定义 关于整数 \(x,y\) 的不定方程 \(ax + by = c\) ,其中 \(a,b,c\) 都是整数,称为二元一次不定方程。

裴蜀定理

定理1(裴蜀定理) 关于整数 \(x,y\) 不定方程 \(ax+by = c\) 有解的充要条件是 \(\gcd(a,b) \mid c\)

推论1 关于整数 \(x,y\) 不定方程 \(ax+by = 1\) 有解的充要条件是 \(\gcd(a,b) = 1\)

推论2\(a,b \geq 1,x,y\geq0\)\(\gcd(a,b) = 1\) 时,\(ax+by\) 一定能表示大于等于 \(ab-a-b+1\) 的数。

定理1的证明:

\(d = \gcd(a,b)\) ,则 \(d \mid ax+by\) ,设 \(s\)\(ax+by\) 的最小正值。

\(q = \left\lfloor \dfrac{a}{s} \right\rfloor\)\(r = a \bmod s\) ,则 \(r = a - qs = a-q(ax+by) = a(1-qx)+b(-qy)\) ,即 \(r\) 也可以被 \(ax+by\) 表示。

因为 \(r \in [0,s-1]\) ,所以 \(r = 0\) ,即 \(s \mid a\) ,同理 \(s \mid b\) 。因此,\(s \mid d\) ,所以 \(s \leq d\)

因为 \(s = ax+by\) ,所以 \(d \mid s\) , 于是 \(d \leq s\)

综上 \(d = s\) ,即 \(\gcd(a,b) = d\)\(ax+by\) 的最小正值。

推论2的证明:

解二元一次不定方程

扩展欧几里得算法

类欧几里得算法

乘法逆元

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

乘法逆元的求法

费马小定理法

扩展欧几里得法

线性求乘法逆元

线性求阶乘逆元

一元一次同余方程

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

解一元一次同余方程

扩展欧几里得算法

解一元一次同余方程组

中国剩余定理

扩展中国剩余定理

本文来自博客园,作者:空白菌,转载请注明原文链接:http://www.cnblogs.com/BlankYang/p/17051072.html

本文转载于网络 如有侵权请联系删除

相关文章

  • 关于 hostapd[通俗易懂]

    大家好,又见面了,我是你们的朋友全栈君。关于hostapd主页:http://w1.fi/hostapd/hostapd是一个IEEE802.11的AP和IEEE802.1X/WPA/WPA2/EAP/RADIUS验证器.此页面用于怎么在linux系统下使用它.其他操作系统请参考hostapd主页就Linux而言,老版本只能使用以下3个包HostAP madwifi prism54 所有新的基于mac80211的驱动实现AP功能被hostapd’snl80211驱动支持Themac80211子系统将所有的master模式已经移到用户空间.通过hostapd去处理客户端验证,设置加密密钥,建立密钥转化策略,以及无线公共部分的其他方面.由此,老的使用’iwconfig<wirelessinterface>modemaster’的方法已经不能使用了.用户空间程序像hostapd目前使用netlink(thenl80211driver)去创建mastermode接口实现通信,monitormode接口实现接收和发送管理框架获得hostapdUsingyourdistribution

  • [PHP] php使用phpoffice/phpexcel 生成excel文件

    使用这个php依赖扩展非常简单,直接引入composerrequirephpoffice/phpexcel使用方式按下面这样$objPHPExcel=new\PHPExcel(); try{ $objSheet=$objPHPExcel->getActiveSheet(); //工作表标题 $objSheet->setTitle("外呼结果"); //第一行内容,放列标题 $objSheet->setCellValue("A1","城市"); $objSheet->setCellValue("B1","阿姨姓名"); $objSheet->setCellValue("C1","阿姨手机号"); $objSheet->setCellValue("D1","渠道"); $objSheet->setCellValue("E1","创建时间&qu

  • 干货 | Elasticsearch 可搜索快照深入详解

    0、可搜索快照认知前提Elasticsearch可搜索快照是7.10版本才有的新功能,之前呼声非常高。Elastic官方网站用一整页面介绍,可见对该功能的重视。https://www.elastic.co/cn/elasticsearch/elasticsearch-searchable-snapshots但,有个细节要跟大家强调:该功能是企业版本才有的收费功能,黄金版、白金版、基础免费开源版本都不具备该功能。本文的相关实战验证,是基于30天试用版本做的验证。1、什么是可搜索快照?讲可搜索快照的定义前,先说一下大数据的存储。对于小微企业来讲,硬件成本是产品、项目环节非常重要的考量因素。数据量的激增和项目的经费之间本来就是相生相克、相爱相杀的关系。一方面:老板要控制成本的前提下满足甲方的功能需求、性能需求且追求利润最大化。另一方面:开发人员为满足性能指标最大程度的优化,多少会涉及提升硬件资源配置的需求,比如:换SSD磁盘、加内存或更换CPU。老板会说:经费有限,给老子优化性能,尽一切可能满足甲方的需求。开发人员心里暗自嘀咕:不给老子提升资源配置,我优化个毛线。当听说字节跳动线上环境:最小

  • Google 基础架构安全设计概述

    Google基础架构安全设计概述本文包含的内容截至2017年1月是正确无误的,代表截至本文撰写之时的现状。由于我们会不断完善对客户的保护,因此Google的安全政策和制度可能会随着时间的推移而发生变化。首席信息官级别的摘要 Google拥有全球规模的技术基础架构,该基础架构旨在让Google能够在整个信息处理周期提供安全保障。该基础架构可实现以下用途:安全地部署服务;在保护最终用户隐私的情况下安全地存储数据;在服务之间安全通信;通过互联网安全而私密地与客户进行沟通;使管理员能安全地进行操作。Google利用该基础架构来构建其互联网服务,包括Google搜索、Gmail和Google相册等个人用户服务以及GSuite和GoogleCloudPlatform等企业服务。基础架构的安全性是分层级逐步实现的,先从数据中心的物理安全性开始,接着是构成基础架构基础的硬件和软件的安全性,最后是通过技术限制和流程实现运营安全性。为了确保基础架构的安全,Google投入了巨大的成本,雇用了数百名致力于安全与隐私保护的工程师,他们分布在各个Google公司,其中许多人是公认的业界权威。简介本文档概述了如何

  • Flutter基础widgets教程-IntrinsicHeight篇

    1IntrinsicHeight一个widget,它将它的子widget的高度调整其本身实际的高度2构造函数IntrinsicHeight({ Keykey, Widgetchild })复制3常用属性3.1child:子widgetchild:Text('你好Flutter'),复制

  • 剑指Offer - 面试题18. 删除链表的节点

    1.题目给定单向链表的头指针和一个要删除的节点的值,定义一个函数删除该节点。 返回删除后的链表的头节点。注意:此题对比原题有改动示例1: 输入:head=[4,5,1,9],val=5 输出:[4,1,9] 解释:给定你链表中值为5的第二个节点,那么在调用了你的函数之后, 该链表应变为4->1->9. 示例2: 输入:head=[4,5,1,9],val=1 输出:[4,5,9] 解释:给定你链表中值为1的第三个节点,那么在调用了你的函数之后, 该链表应变为4->5->9. 说明:题目保证链表中节点的值互不相同。复制来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/shan-chu-lian-biao-de-jie-dian-lcof 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。2.解题类似题目:LeetCode203.移除链表元素建立一个哨兵头结点,能统一代码classSolution{ public: ListNode*deleteNode(ListNode*head,intv

  • 深度理解:Openshift端口方式全解析

    一、几种网络端口模式Openshift/Docker中,我们会遇到(听到)的几种网络端口模式有:HostportNodeportHostnetworkrouter 它们有什么区别,适用于什么场景?我们先看看它们的作用。二、什么是hostport?hostport它指的是:在一个宿主机上运行的一个容器,为了外部能够访问这个容器,将容器的端口与宿主机进行端口映射。而为了避免宿主机上的端口占用,在容器和宿主机做端口映射的时候,通常映射一个比较大的端口号(小端口被系统服务占用)。我们看一个实验:在宿主机上启动一个apache的容器,将容器的端口80,映射成宿主机的端口10080.然后,我们查看这个容器的网络模式,可以看到,该容器使用的是hostport的模式,占用宿主机的端口号是10080.我们查看容器的IP,地址为:172.17.0.2接下来,我们验证apache服务。首先,图形化登录宿主机,访问宿主机的80端口(确保宿主机的httpd服务是停止的),无法访问:接下里,访问宿主机的10080端口,可以访问apache网页,说明此时访问的服务,是容器中的:接下来,我们通过外部访问宿主机的域名加

  • 【编程基础】如何理解java中的多态

    大家都知道Java面向对象有几大特征:抽象、封装、继承和多态,Java的这些特性让Java变得很强大,可以很轻松的胜任比较复杂的项目开发。今天重点给大家说说多态这个特性。多态总结起来发生的场景就是两类:1、对象运行时确定是子类还是父类;2、方法运行时确定调用同名的哪个方法;也就是指程序中定义的引用变量所指向的具体类型和通过该引用变量发出的方法调用在编程时并不确定,而是在程序运行期间才确定,即一个引用变量倒底会指向哪个类的实例对象,该引用变量发出的方法调用到底是哪个类中实现的方法,必须在由程序运行期间才能决定。因为在程序运行时才确定具体的类,这样,不用修改源程序代码,就可以让引用变量绑定到各种不同的类实现上,从而导致该引用调用的具体方法随之改变,即不修改程序代码就可以改变程序运行时所绑定的具体代码,让程序可以选择多个运行状态,这就是多态性。向上转型规则:在用一个子类型复制给父类型时,指向子类的父类引用由于向上转型了,它只能访问父类中拥有的方法和属性,而对于子类中存在而父类中不存在的方法,该引用是不能使用的,尽管是重载该方法。若子类重写了父类中的某些方法,在调用该些方法的时候,必定是使用子

  • 242. 有效的字母异位词

    242.有效的字母异位词一、题目描述:给定两个字符串s和t,编写一个函数来判断t是否是s的字母异位词。注意:若s和t中每个字符出现的次数都相同,则称s和t互为字母异位词。示例1:输入:s=“anagram”,t=“nagaram” 输出:true 示例2:输入:s=“rat”,t=“car” 输出:false提示:1<=s.length,t.length<=5*10^4 s和t仅包含小写字母进阶:如果输入字符串包含unicode字符怎么办?你能否调整你的解法来应对这种情况?来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/valid-anagram 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。二、思路分析:这道题考察了什么思想?你的思路是什么? 这道题目用Python还是很容易的,只需要两个字符串之间相减,然后判断是否为空即可。做题的时候是不是一次通过的,遇到了什么问题,需要注意什么细节? 不是一次通过的,刚开始只比较了not(collections.Counter(s)-collections.

  • 有约束最优化问题MATLAB_约束条件下的最优化问题

    最近在做天线多目标优化的实例,因此接触到了NSGA-Ⅱ算法,所以想分享以下我个人的学习内容与经历,仅作参考,如果内容有误,也希望各位能够指出来,大家一起进行交流指正。 内容将分为以下几个模块,内容可能较多,如果觉得不错的话,可以点赞?,收藏或者转发哦!目录NSGA-Ⅱ算法简介非支配集排序锦标赛选择模拟二进制交叉多项式变异精英保留策略参考文献NSGA-Ⅱ算法简介NSGA-Ⅱ算法由Deb等人首次提出,其思想为带有精英保留策略的快速非支配多目标优化算法,是一种基于Pareto最优解的多目标优化算法。 该算法的重要过程为:将进化群体按照支配关系分成若干层,第一层为进化群体中的非支配个体集合,第二层为在进化群体中去掉第一层个体后求得非支配个体集合,第三层,第四层依此类推。 在这里,我就不再赘述NSGA-Ⅱ的具体概念,而是将重点放在如何实现上。想要进行初步学习的可以转至:作者晓风wangchao,标题多目标优化算法(一)NSGA-Ⅱ(NSGA2) 支配集与非支配集的了解可以参考书籍:《多目标进化优化》或者自行百度,csdn中其他的文章。个人觉得这是基本的概念哈,可以自学。 可行解为符合约束条件的解

  • 腾讯云地域管理系统产品简介

    什么是地域管理系统?地域管理系统(RegionManagementSystem)是管理腾讯云地域资源的统一工具。腾讯云用户可通过统一的地域云API获取各个云产品的地域信息,再通过地域信息操作相应资源,有效提升用户运维体验。产品优势操作简单:通过云API操作,极大简化维护地域信息的操作成本。标准统一:腾讯云所有产品都按统一的方式对外暴露地域。应用场景当腾讯云用户需要购买云服务器时,可通过地域管理系统API获取云服务器支持的地域信息,再去相应的地域操作购买云服务器。

  • Ubuntu为PHP安装SOAP扩展

    apt-getinstallphp5.6-soap     3)安装php5.6及常用组件 sudoapt-getinstallphp5.6 sudoapt-getinstallphp5.6-gd sudoapt-getinstallphp5.6-mysql sudoapt-getinstallphp5.6-mbstring sudoapt-getinstallphp5.6-zip sudoapt-getinstallphp5.6-curl   Apache2重启: sudo/etc/init.d/apache2restart

  • 2021个人年度总结

    --辛丑年,愿温语安寄,太平如一       岁末年初,2022已经来了,到了小学作文里写的年份啦 ?。临时起意,盘点下2021的全年事项,记录下个人的收获与反思。希望对制定下一年的目标时有参考价值。 生活方面 1、这一年共读过24本书,读完13本。其中有自己挑选的书,《围城》《晚熟的人》《苏东坡传》都很不错。也有因为通过职场综艺,看到很nice的导师,读完了他的《自洽》,更有看到一半被下架的《成吉思汗》。最近几天在读维克多·弗兰克尔的《活出生命的意义》。     “晚熟的人”伏笔很多,多处相互呼应,后劲很足。尤其最后一章“火把与口哨”,自认为是全文最精彩的一段。“自洽”属于工具书,读的时候很认同,但回味不多。多向微信读书的榜一看齐,下一年争取读更多的书,努力!   2、公众号没怎么进步,输出的原创比去年少,下半年更新频率很低。“断更是从第一次不准时发文开始的”,这句话很像废话,但真的是第一次没坚持住,后面就越没动力。但断断续续的多了近千的粉丝,让我又惊又喜。靠吃老

  • c++类型转换

    异常处理: 栈解旋:在try{}语句块中定义的栈变量,抛出异常时,会自动析构所用的变量。    

  • python模块之Git模块使用

    #!/usr/bin/python #coding:utf8 #@Author:liaojiaf@chanjet.com #@Time:3/17/204:04PM #@Site: #@File:git_handle.py #@IDE:PyCharm fromgitimportGit,Repo importtime classgit_handler(object): def__init__(self,dest_dir): self.repo=Repo(dest_dir) defgit_add(self,add_file="*"): try: index=self.repo.index ifnotisinstance(add_file,list): add_file=[add_file,] ifindex.add(add_file): returnTrue except: returnFalse defgit_remove(self,del_file): index=self.repo.index ifnotisinstance(del_file,list): del_file

  • ROS2安装及使用过程中遇到的问题

    ROS2常规的安装流程在网上可以找到,正常安装基本没问题。但是,由于操作系统和后台运行程序的差异,还是会遇到一些问题。我把我在安装过程中遇到的问题记录如下: 1.安装版本的选择 ROS2有多个发行版(ros_distro),目前出来的有Crystal、Bouncy、Ardent。具体多少个,可去ROS2的网站上去查询。 选择安装版本shell命令: $exportROS_DISTRO=crystal#orbouncyorardent $sudoaptupdate 复制 就是同一个发行版,也分桌面版和基础版: 建议安装桌面版,有界面: $sudoaptinstallros-$ROS_DISTRO-desktop复制 若安装基础版: $sudoaptinstallros-$ROS_DISTRO-ros-base复制 2.ROS2命令不能执行 比如执行一条ros2命令: $ros2rundemo_nodes_cpptalker复制 但shell却提示ros2:commandnotfound。 这时应该检查环境变量ROS_DISTRO的值是否是对应的ROS2发行版名

  • 让对象拥有状态——C#中的状态模式

    大家好,老胡又在博客和大家见面了,在聊今天的主角之前,老胡先给大家讲一个以前发生的故事。   真实的故事 当老胡还是小胡的时候,跟随团队一起开发一款游戏。这款游戏是一款末日生存类游戏,玩家可以 收集资源,两种,一种金子,一种铁。 升级自身 击杀敌人 用资源合成装备 项目开发的很顺利,我那时得到一个任务,是为游戏做一个新手教程,在这个教程里面,通过一系列步骤,引导新手玩家熟悉这个游戏。游戏设计给出的教程包含以下步骤 收集金子 收集铁 击杀敌人 升级 同时要求在不用的阶段显示不同的提示以正确引导玩家。 考虑合成装备算是高级玩家才会接触到的功能,所以暂时不打算放在新手教程里面。 当老大把任务交给我的时候,我感觉简单爆了,不就写一个新手教程么,要求又那么明确,应该要不了多少时间。于是,一个上午过后,我交出了如下代码。   我的代码 定义枚举表示教程进度 首先用一个枚举,表示教程进行的不同程度 enumTutorialState { GetGold, GetIron, KillEnemy, LevelUp } 复制   定义角色类 无需多言,封装收集到的资源

  • sql的Dateadd()函

    在整理单位考勤机导出的数据时刚巧看到Dateadd()的用法 Createprocsp_DateInsert--建立存储过程输入2个日期内的日历@startDatedatetime,@endDatedatetimeasbeginwhile(@startDate<=@endDate)begininsertintotb_timecard_d2(ddate)values(CONVERT(char(8),@startDate,23))set@startDate=DATEADD(day,1,@startdate)endend 相同思路,可以输入年份,季度,月份等。 id

  • IOC容器MEF在MVC中的使用

    最近想把自己的网站框架用IOC改造下,经过对比,我初步选择autofac,虽然MEF不需要配置,但性能不行,autofac虽然需要自己写自动化注入,但性能非常好。 先分析下各大IOC框架的性能,分两类测试,一类是单例,一类的每次注入新的对象。 MEF本来也测试了,但代码放公司,就懒得跑了,性能最好的前三是:Nlite,autofa,MEF,但NLite太轻量了,提供的API不太能满足实际需求,本来打算用MEF,配置简单,但下面的测试让我最终选择了autofa 但今天在并发性测试的时候,发现MEF在高并发情况下会出现未知异常,在使用OutputCache的情况下,使用Lazy模式加载对象会出现性能不好,且急剧下降和不稳定的情况,有少量500错误。 非lazy模式更悲惨,在开始能保持6000多的并发,但一会之后不堪入目啊,还有未知500错误。 在不使用outputcache的情况下,使用IOC的响应时间稍好,但用测试工具跑一会之后会出现错误 用autofac测试无任何错误  

  • English Grammar in Use - Part1 Present and past

    Unit1Presentcontinuous(Iamdoing) A)Am/is/are+-ingisthePresentcontinuous. B)Iamdoingsomething=I'minthemiddleofdoingit;I'vestarteddoingitandIhaven'tfinished. C)Youcanusethepresentcontinuouswithtoday/thisweek/thisyearetc.(preiodaroundnow). D)Weusethepresentcontinuouswhenwetalkaboutchangeshappeningaroundnow,especiallywiththeseverds:   get  change  become  increase  rise  fall  grow  improve  begin  start   eg:IsyourEnglishgettingbetter?(notDoesyourEnglishgetbetter) Exercises: 1.1f,e,g,a,d,h,b,c; 1.2

  • 【前端开发】常见的动画库

    Typed.js 地址:https://mattboldt.com/demos/typed-js/JavaScript打字动画库。 Anime.js 地址:https://animejs.com/具有简单但功能强大的API的轻量级JavaScript动画库。 ProgressBar.js 地址:https://kimmobrunfeldt.github.io/progressbar.js/带有动画SVG路径的响应式和流畅的进度条。 本文来自博客园,作者:JeckHui,转载请注明原文链接:https://www.cnblogs.com/xiaohuizhang/p/15870081.html

相关推荐

推荐阅读