线性同余方程

注意：若无特殊说明，本章涉及的变量皆为正整数.

简介 #

形如 $ax≡c\pmod{b}$ 的方程称为线性同余方程.

特殊解 #

$ax≡c\pmod{b}\eq ax+by=c$. 由裴蜀定理可知，当且仅当 $gcd(a,b)\mid c$ 时有整数解.

先用扩展欧几里得算法求出一组 $x_0,y_0$，使得：

$$ax_0+by_0=gcd(a,b)$$

两边同时乘 $\frac{c}{gcd(a,b)}$：

$$a\frac{c}{gcd(a,b)}x_0+b\frac{c}{gcd(a,b)}y_0=c$$

于是找到方程 $ax+by=c$ 的一组特殊解：

$$\left\{\begin{aligned} x=\frac{c}{gcd(a,b)}x_0\\ y=\frac{c}{gcd(a,b)}y_0 \end{aligned}\right.$$

通解 #

若 $x_0,y_0$ 为方程 $ax+by=c$ 的一组解，则该方程的任意解可表示为：

$$\left\{\begin{aligned} x=x_0+bt\\ y=y_0-at \end{aligned}\right.$$

在实际问题中，往往只需要最小正整数解：

$$x=(x_0 \bmod t+t) \bmod t, \ t=\frac{b}{gcd(a,b)}$$

模板 #

int exGcd(int a, int b, int& x, int& y) {
    if (b == 0) { x = 1, y = 0; return a; }
    int d = exGcd(b, a % b, x, y);
    int t = x; x = y, y = t - a / b * y;
    return d;
}

int liEu(int a, int b, int c) { // ax ≡ c (mod b)
    int x, y, d = exGcd(a, b, x, y);
    if (c % d != 0) return -1;          // 没有整数解
    return x * (c / d);                 // 特殊解
    // int t = b / d;
    // return x = (x % t + t) % t;      // 最小正整数解
}