同余方程、中国剩余定理、扩展中国剩余定理、高次同余式

(1.) 一次同余方程

[axequiv b (mod m) ]

(1.1) 一次同余方程概述

设方程的一个特解为 (x_{0})，那么方程的通解即为

[xequiv x_{0} (mod m) ]

设 (a^{-1}) 为 (a) 在模 (m) 意义下的逆元

那么解的情况可以归纳为

(1)) 若 ((a, m) = 1)，则方程有一解

[xequiv bcdot a^{-1} (mod m) ]

(2)) 若 ((a, m) > 1)

若 ((a, m)mid b)，则方程有 ((a, m)) 个解

[xequiv frac{a}{(a, m)}^{-1}cdot frac{b}{(a, m)} (mod frac{m}{(a, m)}) + rcdot frac{m}{(a, m)} (mod m), r = 0, 1, ..., (a, m) - 1 ]
若 ((a, m) mid b)，则方程无解

(1.2) 一次同余方程方程解的情况证明

为了方便叙述，记 ((a, m) = d)

(1.2.1) (d = 1) 的情况

[axequiv b (mod m) ]

上述方程存在唯一解 (x_{0})，满足 (x_{0}equiv bcdot a^{-1} (mod m))

证明：

先证明存在性

即证明，若 (d = 1)，上述方程存在解

考虑方程

[axequiv 1 (mod m) ]

由于 (d = 1) ，所以

[exists s, tin mathbb{Z}, sa + tm = 1 ]

所以 (s) 即为方程

[axequiv 1 (mod m) ]

的一个特解

事实上， (sequiv a^{-1} (mod m))

将其乘以 (b)，得到方程

[axequiv b (mod m) ]

的解为

[xequiv a^{-1}b (mod m) ]

至此，存在性证毕！

下证唯一性

设方程

[axequiv b (mod m) ]

有两个特解 (x_{1}, x_{2})

则

[a(x_{1} - x_{2})equiv 0 (mod m) ]

由于 ((a, m) = 1) ，所以 (x_{1}equiv x_{2} (mod m))

唯一性证毕！

(1.2.2) (d > 1) 的情况

[axequiv b (mod m) ]

若 (dmid b)，方程有 (d) 个解

若 (d mid b)，方程无解

先证明必要性

即证明，若方程有解，则 (dmid b)

由于 (d = (a, m))，所以 (dmid a, dmid m)，所以 (dmid ax)

又 (axequiv b (mod m))，所以 (mmid ax - b)

所以 (dmid ax - b)

所以 (dmid b)

必要性证毕！

下证明充分性

考虑方程

[frac{a}{d}cdot xequiv frac{b}{d} (mod frac{m}{d}) ]

由于 ((frac{a}{d}, frac{m}{d}) = 1)

所以上述方程存在解

[xequiv frac{b}{d}cdot (frac{a}{d})^{-1} (mod frac{m}{d}) ]

通解可以写为

[x = frac{b}{d}cdot (frac{a}{d})^{-1} (mod frac{m}{d}) + qcdot frac{m}{d} ]

带一点技巧性地

设

[q = kcdot d + r, r = 0, 1, ..., d - 1 ]

所以通解可以变为

[frac{b}{d}cdot (frac{a}{d})^{-1} (mod frac{m}{d}) + kcdot m + rcdot frac{m}{d}, qin mathbb{Z} ]

于是

[xequiv left[frac{b}{d}cdot (frac{a}{d})^{-1} (mod frac{m}{d}) + rcdot frac{m}{d} ight] (mod m), r = 0, 1, ..., d - 1 ]

由于 (r) 有 (d) 个值，所以方程的解有 (d) 个

充分性证毕！

(1.3) 一次同余方程 (code)

多组数据按顺序读入 (a, b, m)，多个解按照从小到大的顺序输出

#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int, int>
#define arrayDebug(a, l, r) for(int i = l; i <= r; ++i) printf("%d%c", a[i], " 
"[i == r])
typedef long long LL;
typedef unsigned long long ULL;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
const int DX[] = {0, -1, 0, 1, 0, -1, -1, 1, 1};
const int DY[] = {0, 0, 1, 0, -1, -1, 1, 1, -1};
const int MOD = 1e9 + 7;
const int N = 1e6 + 7;
const double PI = acos(-1);
const double EPS = 1e-6;
using namespace std;

inline int read()
{
    char c = getchar();
    int ans = 0, f = 1;
    while(!isdigit(c)) {if(c == '-') f = -1; c = getchar();}
    while(isdigit(c)) {ans = ans * 10 + c - '0'; c = getchar();}
    return ans * f;
}

int exgcd(int a, int b, int &x, int &y)
{
    if(!b) {x = 1, y = 0; return a;}
    int r = exgcd(b, a % b, y, x);//y的值被修改为x'，x的值被修改为y'
    y -= a / b * x;
    return r;
}

int cnt, ans[N] = {0};
int main()
{
    int a, b, m;
    while(cin >> a >> b >> m){
        cnt = 0, memset(ans, 0, sizeof(ans));
        int x, y;
        int d = exgcd(a, m, x, y);
        if(b % d) puts("No Answer.");
        else {
            int r = exgcd(a / d, m / d, x, y);
            while(x < 0) x += m / d;
            for(int i = 0; i < d; ++i)
                ans[++cnt] = (b / d * x + i * m / d) % m;
            sort(ans + 1, ans + 1 + cnt);
            for(int i = 1; i <= cnt; ++i)
                printf("%d%c", ans[i], " 
"[i == cnt]);
        }
    }
    return 0;
}

(2.) 中国剩余定理

给定线性同余方程组

[left{egin{matrix} x_{1}equiv a_{1} (mod m_{1}) \x_{2}equiv a_{2} (mod m_{2}) \... \x_{n}equiv a_{n} (mod m_{n}) end{matrix} ight. ]

保证 (m_{1}, m_{2}, ... m_{n}) 两两互质

(2.1) 中国剩余定理 (CRT) 概述

设

[m = prod_{i = 1}^{n}m_{i} ]

以及

[M_{i} = frac{m}{m_{i}}, i = 1, 2, ..., n ]

则上述同余方程组的通解为

[xequiv sum_{i=1}^{n}a_{i}cdot M_{i}cdot M_{i}^{-1} (mod m_{i}) (mod m) ]

(2.2 CRT) 解的求解与证明

考虑对于每一个线性同余方程

[x_{i}equiv a_{i} (mod m_{i}) ]

求出对应的一个特解 (x_{i}) ，且这个 (x_{i}) 要满足

[left{egin{matrix} x_{i}equiv a_{j} (mod m_{j}), i=j \x_{i}equiv 0 (mod m_{j}), i eq j end{matrix} ight. ]

把 (n) 个这样的 (x_{i}) 求和，就可以得到方程组的一个特解 (x)

设

[m = prod_{i = 1}^{n}m_{i} ]

以及

[M_{i} = frac{m}{m_{i}}, i = 1, 2, ..., n ]

分析 (x_{i}) ，其必然是 (M_{i}) 的整数倍，且满足

[x_{i}equiv a_{i} (mod m_{i}) ]

设

[x_{i}=ycdot M_{i}, yin mathbb{Z} ]

有

[ycdot M_{i}equiv a_{i} (mod m_{i}) ]

只要能够解出 (y) ，便能得到 (x) 的特解；反之，线性同余方程组无解

因为 ((M_{i}, m_{i}) = 1)

所以由扩欧算法得到

[yequiv a_{i}cdot M_{i}^{-1} (mod m_{i}) ]

所以

[x_{i} = a_{i}cdot M_{i}cdot M_{i}^{-1} (mod m_{i}) ]

将 (n) 个 (x_{i}) 求和得到 (x) 的一个特解

[x=sum_{i=1}^{n}a_{i}cdot M_{i}cdot M_{i}^{-1} (mod m_{i}) ]

为了满足题意， (x) 的通解为

[xequiv sum_{i=1}^{n}a_{i}cdot M_{i}cdot M_{i}^{-1} (mod m_{i}) (mod m) ]

特殊的， (x) 的最小非负解为

[x mod m ]

(2.3 CRT code)

int n, a[N], p[N];
LL M = 1;

int exgcd(int a, int b, int &x, int &y)
{
    if(!b) {x = 1, y = 0; return a;}
    int r = exgcd(b, a % b, y, x);//y的值被修改为x'，x的值被修改为y'
    y -= (a / b) * x;
    return r;
}

int inv(int a, int p)
{
    int x = 0, y = 0;
    int gcd = exgcd(a, p, x, y);
    while(x < 0) x += p;
    return x;
}
int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    for(int i = 1; i <= n; ++i)
        scanf("%d", &p[i]);
    for(int i = 1; i <= n; ++i)
        M *= p[i];
    int x = 0;
    for(int i = 1; i <= n; ++i){
        x += a[i] * inv(M / p[i], p[i]) * M / p[i], x %= M;
    }
    printf("%d
", x);
    return 0;
}

(3.) 扩展中国剩余定理

给定线性同余方程组

[left{egin{matrix} x_{1}equiv a_{1} (mod m_{1}) \x_{2}equiv a_{2} (mod m_{2}) \... \x_{n}equiv a_{n} (mod m_{n}) end{matrix} ight. ]

(m_{1}, m_{2}, ... m_{n}) 不一定两两互质

(3.1) 扩展中国剩余定理概述

设

[m = [m_{1}m_{2}...m_{n}] ]

则上述方程组通解为

[x = x_{0} + qcdot frac{m_{i}}{gcd(m, m_{i})}, qin Z ]

其中 (x_{0}) 是同余方程组的一个特解，通过 (n - 1) 次扩欧算法计算得出

(3.2 EXCRT) 的解

考虑已经解出前 (k-1) 个方程的解 (x_{1})

习惯的，我们设

[m=prod_{i=1}^{k-1}m_{i} ]

但为了防止溢出，设

[m=[m_{1}, m_{2},.., m_{k - 1}] ]

那么前 (k-1) 个方程的通解为

[xequiv x_{1} (mod m) ]

设 (x_{2} = x_{1} + tcdot m, tin mathbb{Z})

将 (x_{2}) 代入第 (k) 个式子

[x_{1} + tcdot mequiv a_{k} (mod m_{k}) ]

即

[tcdot mequiv a_{k} - x_{1} (mod m_{k}) ]

若

[(m, m_{k}) mid a_{k} - x_{1} ]

则线性同余方程组无解

若

[(m, m_{k})mid a_{k} - x_{1} ]

由扩欧算法解出 (t)，得到特解 (x_{2})

那么新的通解为

[xequiv x_{2} (mod m_{k}) ]

如此循环

(excrt) 的本质便是合并方程

对于 (n) 个方程的线性同余方程组，本质上是作 (n-1) 次扩展欧几里得算法

(3.3) (EXCRT code)

处理到第 (k) 个方程时，具体求 (x_{2}) 的过程如下

因为

[x_{2} = x_{1} + tcdot m ]

其中

[m = [m_{1}m_{2}...m_{k - 1}] ]

所以即在方程中求 (t)

[tcdot mequiv a_{k} - x_{1} (mod m_{k}) ]

先用扩欧求方程

[tcdot m + qcdot m_{k} = (m, m_{k}) ]

的特解 (t_{0})，然后自乘系数

[frac{a_{k} - x_{1}}{(m, m_{k})} ]

进而得到通解

[t = t_{0}cdot frac{a_{k} - x_{1}}{(m, m_{k})} + qcdot frac{m_{k}}{(m, m_{k})}, qin mathbb{Z} ]

为了防止溢出，将 (t) 取模数 (frac{m_{k}}{(m, m_{k})}) 至最小非负数

于是得到

[x_{2} = x_{1} + tcdot m ]

int n;
LL a[N], p[N];

LL qmul(LL a, LL b, LL mod)
{
    LL res = 0;
    while(b > 0) {
        if(b & 1) res += a, res %= mod;
        a += a, a %= mod;
        b >>= 1;
    }
    return res;
}

LL exgcd(LL a, LL b, LL &x, LL &y)
{
    if(!b) {x = 1, y = 0; return a;}
    LL r = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return r;
}

LL excrt(LL n, LL *a, LL *p)
{
    LL M = p[1];//维护LCM
    LL x = a[1];//维护解
    for(int i = 2; i <= n; ++i){
        LL xx = 0, yy = 0;
        LL gcd = exgcd(M, p[i], xx, yy);
        LL c = (a[i] - x % p[i] + p[i]) % p[i];
        LL ag = p[i] / gcd;
        if(c % gcd) return -1;
        c /= gcd;
        //若数据较大，使用快速乘防止溢出
        //LL t = qmul(xx, c, ag);
        LL t = (xx * c) % ag;
        x += t * M;//得到新的特解
        M *= ag;//更新LCM
        x = (x % M + M) % M;//将x更新到最小
    }
    return x;
}
int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
        scanf("%lld %lld", &p[i], &a[i]);
    LL ans = excrt(n, a, p);
    if(ans == -1) puts("-1");
    else printf("%lld
", ans);
    return 0;
}

(4.) 求解高次同余式

设

[f(x) = sum_{i = 0}^{n}a_{i}x^{i} ]

求解

[f(x)equiv 0 (mod m) ]

(4.1) 解高次同余式的等价以及解的数量

求高次同余式

[f(x)equiv 0 (mod m) ]

等价于

求高次同余式组

[left{egin{matrix} f(x)equiv 0 (mod m_{1}) \f(x)equiv 0 (mod m_{2}) \... \f(x)equiv 0 (mod m_{n}) end{matrix} ight. ]

证明思路如下

设方程 (f(x)equiv 0 (mod m_{i})) 为 (T_{i})

设方程 (f(x)equiv 0 (mod m)) 为 (T)

只要证明，方程组 (T_{i}) 的所有解都是方程 (T) 的解，以及方程 (T) 的所有解都是方程组 (T_{i}) 的解即可

先证明，方程组 (T_{i}) 的所有解都是方程 (T) 的解

若对于任意 (i)，都有 (f(x_{0})equiv 0 (mod m_{i}))

那么说明 (f(x_{0})) 是 (m_{1}, m_{2}, ..., m_{n}) 的公倍数

而 (m = m_{1}m_{2}...m_{n} = [m_{1}m_{2}...m_{n}])

所以 (f(x_{0})equiv 0 (mod m))

设方程 (T_{i}) 的解为 (xequiv b_{i} (mod m_{i}))

则

[left{egin{matrix} xequiv b_{1} (mod m_{1}) \xequiv b_{2} (mod m_{2}) \... \xequiv b_{n} (mod m_{n}) end{matrix} ight. ]

由中国剩余定理，方程组 (T_{i}) 的解为

[xequiv sum_{i=1}^{n}b_{i}cdot M_{i}cdot M_{i}^{-1} (mod m_{i}) (mod m) ]

有

[f(x)equiv f(b_{i})equiv 0 (mod m_{i}) ]

所以

[f(x)equiv 0 (mod m) ]

即方程组 (T_{i}) 的所有解都是方程 (T) 的解

下证明，方程 (T) 的所有解都是方程组 (T_{i}) 的解

若 (f(x)equiv 0 (mod m))

则 (f(x)equiv 0 (mod m_{i}))

这是因为 (m_{i}mid mmid f(x))

所以方程 (T) 的所有解都是方程组 (T_{i}) 的解

(Q.E.D.)

设 (T_{i}) 解的数量为 (t_{i})，(T) 解的数量为 (t)

由乘法原理知道

[t = prod_{i = 1}^{n}t_{i} ]

(4.2) 求解模为素数幂的高次同余式

(4.2.1) 概述及其意义

对于整系数高次多项式

[f(x) = a_{n}x^{n} + a_{n - 1}x^{n - 1} + ... + a_{0} ]

考虑同余方程

[f(x)equiv 0 (mod p^{alpha}) ]

若方程有一个解

[xequiv x_{1} (mod p) ]

且

[(f'(x_{1}), p) = 1 ]

则上述同余式有解

[xequiv x_{alpha} (mod p^{alpha}) ]

其中有递推关系如下

[x_{i}equiv x_{i - 1} + t_{i - 1}cdot p^{i - 1} (mod p^{i}) ]

[t_{i - 1}equiv frac{-f(x_{i - 1})}{p^{i - 1}}cdot (f'(x_{1})^{-1} (mod p)) (mod p) ]

[i = 2, 3, ...., alpha ]

由于任何数都可以被分解成素数幂的积的形式，结合高次同余式解的等价，所以解任何模数的高次同余方程，都可以化为求解模为素数幂的情况

(4.2.2) 解的证明

[f(x) = a_{n}x^{n} + a_{n - 1}x^{n - 1} + ... + a_{0} ]

对 (alphageq 2) 做数学归纳法证明

(1)) 当 (alpha = 2) 时

同余式有解

[xequiv x_{1} (mod p) ]

设

[x_{2} = x_{1} + t_{1}cdot p, qin mathbb{Z} ]

下解

[f(x_{1} + t_{1}cdot p)equiv 0 (mod p^2) ]

考虑多项式

[f(x_{1} + t_{1}cdot p) = a_{n}(x_{1} + t_{1}cdot p)^{n} + a_{n - 1}(x_{1} + t_{1}cdot p)^{n - 1} + ... + a_{1}(x_{1} + t_{1}cdot p) + a_{0}) ]

由小学二年级学会的二项式定理

[a_{n - i}cdot(x_{1} + t_{1}cdot p)^{n - i} = a_{n - i}cdot sum_{j = 0}^{n - i}C_{n - i}^{j}cdot x_{1}^{n - i - j}cdot ({t_{1}p})^{j} ]

即

[a_{n - i}cdot (x_{1}^{n - i} + (n - i)cdot x_{1}^{n - i - 1}cdot (t_{1}p) + sum_{j = 2}^{n - i}C_{n - i}^{j}cdot x_{1}^{n - i - j}cdot ({t_{1}p})^{j}) ]

得到

[f(x_{1} + t_{1}cdot p) = (a_{n}x_{1}^{n} + a_{n - 1}x_{1}^{n - 1} + ... + a_{0}) + t_{1}cdot pcdot (a_{n}cdot nx_{1}^{n - 1} + a_{n - 1}cdot(n - 1) x_{1}^{n - 1} + ... + a_{1}) + p^2cdot A ]

即

[f(x_{1} + t_{1}cdot p) = f(x_{1}) + t_{1}pcdot f'(x_{1}) + Acdot (t_{1}p)^2 ]

其中 (Ain mathbb{Z})

所以

[f(x_{1} + t_{1}cdot p)equiv f(x_{1}) + t_{1}pcdot f'(x_{1}) (mod p^2) ]

即解

[f(x_{1}) + t_{1}pcdot f'(x_{1})equiv 0 (mod p^2) ]

由于

[f(x_{1})equiv p (mod p) ]

所以

[t_{1}cdot f'(x_{1})equiv -frac{f(x_{1})}{p} (mod p) ]

这一步用到的定理如下：
若 (d) 是 (a, b, m) 的公因数
则 (aequiv b (mod m)Leftrightarrow frac{a}{d}equiv frac{b}{d} (mod frac{m}{d}))
简易证明如下：
若 (aequiv b (mod m))，则 (mmid (a - b))
若 (dmid a, b, m)
则 (frac{m}{d}mid frac{a}{d} - frac{b}{d})，即 (frac{a}{d}equiv frac{b}{d} (mod frac{m}{d}))

结合 ((f'(x_{1}, p)) = 1)，两边同时乘以 (f'(x_{1})) 在模 (p) 意义下的逆元

即

[t_{1}equiv -frac{f(x_{1})}{p}cdot (f'(x_{1}) (mod p)) (mod p) ]

求出了 (t_{1})，对应的 (x_{2} = x_{1} + t_{1}cdot p) 便满足

[f(x_{2} = x_{1} + t_{1}cdot p)equiv 0 (mod p^2) ]

得证！

(2)) 假设 (alpha = k) 时，有 (x_{k}) 满足 (f(x_{k})equiv 0 (mod p^{k}))

且有

[x_{i} = x_{i - 1} + t_{i - 1}cdot p^{i - 1}, i = 2, 3, ...., k ]

则 (alpha = k + 1) 时，求解

[f(x_{k + 1})equiv 0 (mod p^{k + 1}) ]

设 (x_{k + 1} = x_{k} + t_{k}cdot p^{k})，代入上式得到

[f(x_{k}) + t_{k}p^{k}cdot f'(x_{k}) + Acdot (t_{k}p^{k})^2, Ain mathbb{Z} ]

由于 (2kgeq k + 1)

所以

[f(x_{k}) + t_{k}p^{k}cdot f'(x_{k})equiv 0 (mod p^{k + 1}) ]

由归纳假设， (f(x_{k})equiv 0 (mod p^{k}))

所以

[f'(x_{k})cdot t_{k}equiv -frac{f(x_{k})}{p^k} (mod p) ]

由于

[x_{i} = x_{i - 1} + t_{i - 1}cdot p^{i - 1}, i = 2, 3, ...., k ]

所以

[f'(x_{k})equiv f'(x_{k - 1})equiv...equiv f'(x_{1}) (mod p) ]

结合 ((f'(x_{1}), p) = 1)，知道 ((f'(x_{k}), p) = 1)

考虑两边同时乘以 (f'(x_{k})) 在模 (p) 意义下的逆元

所以

[t_{k}equiv -frac{f(x_{k})}{p^k}cdot (f'(x_{k}) (mod p)) (mod p) ]

即

[t_{k}equiv -frac{f(x_{k})}{p^k}cdot (f'(x_{1}) (mod p)) (mod p) ]

求出了 (t_{k})，对应的 (x_{k + 1} = x_{k} + t_{k}cdot p^{k}) 便满足

[f(x_{k + 1} = x_{k} + t_{k}cdot p^{k})equiv 0 (mod p^{k + 1}) ]

所以 (alpha = k + 1) 时也成立

综上所述，命题得证！