若干类型的同余方程的解法

以下字母未加说明都表示使意义成立的等式

所有的证明、推导都写在引用里了，不愿意看可以跳过。

线性同余方程

解形如

$$ax\equiv c(\mathrm{mod}b)$$

的同余方程.

容易根据同余的定义转化为解形如

$$ax+by=c$$

的二元一次不定方程.

结论 1 该不定方程有整数解的充要条件为 $\gcd (a,b)\mid c$.（裴蜀定理）

证明：
必要性
若 $ax+by=c$ 有整数解 $(x_0,y_0)$，则由于 $\gcd (a,b)\mid a,\gcd (a,b)\mid b$，有 $\gcd (a,b)\mid (a{x}_0+b{y}_0)$，即 $\gcd (a,b)\mid c$.
充分性
若方程 $ax+by=\gcd (a,b)$ 有整数解 $(x_0,y_0)$，则方程 $ax+by=c$ 对应有整数解 $\left(x_0\cdot \frac{c}{\gcd (a,b)},y_0\cdot \frac{c}{\gcd (a,b)}\right)$
故下证 $ax+by=\gcd (a,b)$ 必有整数解.
首先由于 $\gcd (a,b)\mid a,gcd(a,b)\mid b$，则对于 $a,b$ 的任意线性组合，有 $\gcd (a,b)\mid (ax+by)$. 设 $s$ 为 $ax+by$ 的最小正值，且满足 $s=a{x}_0+b{y}_0$，则有 $\gcd (a,b)|s$.
但对于 $a\mathrm{mod}s=a-\lfloor \frac{a}{s}\rfloor s=a-\lfloor \frac{a}{s}\rfloor (a{x}_0+b{y}_0)=a(1-\lfloor \frac{a}{s}\rfloor x_0)+b(-\lfloor \frac{a}{s}\rfloor y_0)$ 也为 $a,b$ 的线性组合，则 $a\mathrm{mod}s\le 0$ 或 $a\mathrm{mod}s\ge s$. 故 $a\mathrm{mod}s=0$，即 $s\mid a$，同理 $s\mid b$，从而 $s\mid \gcd (a,b)$. 又 $\gcd (a,b)\mid s$，所以 $s=\gcd (a,b)$，故 $ax+by=\gcd (a,b)$ 有解 $(x_0,y_0)$.

结论 2 若 $ax+by=c,(a\perp b)$ 的一组特解为 $(x_0,y_0)$，则其所有的解为

{ x = x 0 + b t y = y 0 − a t   ( t ∈ Z )

\ (t\in \mathrm Z) {x=x0​+bty=y0​−at​ (t∈Z)

证明：先证该组 $(x,y)$ 为原方程的解：
$ax+by=a(x_0+bt)+b(y_0-at)=a{x}_0+b{y}_0=1$；
再证这是所有的解. 对于 $ax+by=1$ 的任意一组解 $(x^{\prime },y^{\prime })$，有 $a{x}^{\prime }+b{y}^{\prime }=1$，故 $a(x^{\prime }-x_0)+b(y^{\prime }-y_0)=0$，故 $a\mid b(y^{\prime }-y_0)$
又 $a\perp b$，则 $a\mid (y^{\prime }-y_0)$，则 $y^{\prime }-y_0=ka$. 容易化为题给形式.

推论 若 $ax+by=c$ 的一组特解为 $(x_0,y_0)$，则其所有的解为

{ x = x 0 + b gcd ⁡ ( a , b ) ⋅ t y = y 0 − a gcd ⁡ ( a , b ) ⋅ t   ( t ∈ Z )

\ (t \in \mathrm Z) ⎩ ⎨ ⎧​x=x0​+gcd(a,b)b​⋅ty=y0​−gcd(a,b)a​⋅t​ (t∈Z)

解方程的过程

Step 1 对于方程 $ax+by=c$，其中 $\gcd (a,b)\mid c$，我们先找出 $ax+by=\gcd (a,b)$ 的一组特解.

由于 $ax+by=\gcd (a,b)=\gcd (b,a\mathrm{mod}b)$，若我们先解出了方程 $b{x}^{\prime }+(a\mathrm{mod}b)y^{\prime }=\gcd (b,a\mathrm{mod}b)$ 的一组特解 $(x_0^{\prime },y_0^{\prime })$（这是一个递归过程），我们想办法从 $(x_0^{\prime },y_0^{\prime })$ 推出 $(x,y)$ 的一组解.
由 $\gcd (a,b)=\gcd (b,a\mathrm{mod}b)$，则 $a{x}_0+b{y}_0=b{x}_0^{\prime }+(a\mathrm{mod}b)y^{\prime }$，即 $a{x}_0+b{y}_0=b{x}_0^{\prime }+(a-\lfloor a/b\rfloor b)y_0^{\prime }=a{y}_0^{\prime }+b(x_0^{\prime }-\lfloor a/b\rfloor y_0^{\prime })$.
所以可以令 $x_0=y_0^{\prime },y_0=x_0^{\prime }-\lfloor a/b\rfloor y_0^{\prime }$，得到方程 $ax+by=\gcd (a,b)$ 的一组解。

由上述过程我们容易得到算法：

def solve(a,b) : # 求解 ax+by=\gcd(a,b)
   if b != 0 :   # 递归求解 bx+(a % b)y=\gcd(b,a % b)
      x, y = solve(b, a % b) # 得到 x'_0, y'_0
      return y, x - (a // b) * y # 得到 x_0,y_0
   else :
      return 1, 0
      # 边界情况，此时方程为 ax=a，有解 (1,0)
1
2
3
4
5
6
7

Step 2 我们得到 $ax+by=\gcd (a,b)$ 的特解 $(x_0,y_0)$，则 $ax+by=c$ 的解为 $\left(x_0\cdot \frac{c}{\gcd (a,b)},y_0\cdot \frac{c}{\gcd (a,b)}\right)$

Step 3 我们得到 $ax+by=c$ 的特解为 $(x_0,y_0)$（注意这里的定义和 Step 2 不一样），则其通解为

{ x = x 0 + b gcd ⁡ ( a , b ) ⋅ t y = y 0 − a gcd ⁡ ( a , b ) ⋅ t   ( t ∈ Z )

\ (t\in \mathrm Z) ⎩ ⎨ ⎧​x=x0​+gcd(a,b)b​⋅ty=y0​−gcd(a,b)a​⋅t​ (t∈Z)

一些细节：

1. 解方程之前需要用裴蜀定理判断是否有解。
2. 使用 solve 时保证 a, b 均非负。