模线性方程 ax ≡ b (mod m) 解释

模线性方程 ax ≡ b (mod m) 表示找到一个整数 x，使得 a 乘以 x 与 b 在模 m 下同余。其中，a、b、m 都是整数，且 m 必须为正整数。

例如，方程 2x ≡ 3 (mod 5) 的解为 x = 4，因为 2 * 4 = 8，而 8 在模 5 下与 3 同余。

求解模线性方程的方法是利用扩展欧几里得算法求解 a 和 m 的最大公约数，并根据最大公约数判断方程是否有解以及解的个数。如果 a 和 m 的最大公约数能够整除 b，则方程有解；否则，方程无解。

对于有解的方程，可以使用扩展欧几里得算法求解方程的解。扩展欧几里得算法可以找到两个整数 s 和 t，使得 as + mt = gcd(a, m)，其中 gcd(a, m) 是 a 和 m 的最大公约数。根据这个等式，可以得到方程 x = s * (b / gcd(a, m)) 的解。

模线性方程在密码学、数论等领域有广泛应用。例如，RSA 公钥加密算法就利用了模线性方程的性质。