Modular Linear Equation
模线性方程 ax≡b (mod n) 的求解：当且仅当 gcd(a,n)|b 时有解，共有 gcd(a,n) 个解。
用途
求解模方程，理解模算术下除法不总是可行的条件。
机制
令 d=gcd(a,n)。若 d 不整除 b 则无解。否则用扩展欧几里得求 a/d * x0 ≡ b/d (mod n/d) 的唯一解，全部解为 x0 + k*(n/d) mod n, k=0..d-1。
用例
- 密码学方程求解
- 模算术
- 数论计算
模线性方程 ax≡b (mod n) 的求解：当且仅当 gcd(a,n)|b 时有解，共有 gcd(a,n) 个解。
求解模方程，理解模算术下除法不总是可行的条件。
令 d=gcd(a,n)。若 d 不整除 b 则无解。否则用扩展欧几里得求 a/d * x0 ≡ b/d (mod n/d) 的唯一解，全部解为 x0 + k*(n/d) mod n, k=0..d-1。