INFO

若无特殊说明，本章涉及的变量皆为正整数。

简介

形如 $ax\equiv c(\mathrm{mod}b)$ 的方程称为线性同余方程。

特殊解

$ax\equiv c(\mathrm{mod}b)\iff \mathrm{\exists }y,ax+by=c$。由裴蜀定理知，当且仅当 $\gcd (a,b)\mid c$ 时有整数解。

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

$$a{x}_0+b{y}_0=\gcd (a,b)$$

两边同乘 ${\displaystyle \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$ 的一组特殊解：

$$\{\begin{array}{r}x=\frac{c}{\gcd (a,b)}{x}_0\\ y=\frac{c}{\gcd (a,b)}{y}_0\end{array}$$

通解

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

$$\{\begin{array}{r}x=x_0+bt\\ y=y_0-at\end{array}$$

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

$$x=(x_{0}modt+t)modt,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;      // 最小正整数解
}