ax≡b (mod n) 意指 ax = b + nk', k' \in Z 换句话说就是 ax + nk = b, (k = -k'),所以可以用Extended Euclidean algorithm求解 以 9x≡21 (mod 30) 举例： 求解 9x + 30k = (9, 30) = 3 回忆高中的辗转相除 | 30 | 9 | 3(2) (1)3 | 27 | 3 | |----|----| | 3 | 0 | 所以最大公因数就是 3。现在改用以下形式写： | 0a + 1n | 1a + 0n | (1)3| 3a + 0n | | | --------- | | | -3a + 1n | | 注意这两个算式之间位置的对应， 0a + 1n = 30，1a + 0n = 9 而要扣多少都是由上面那个数字的辗转相除得来的 所以算下来就得到 -3a + 1n = 3 = (9, 30) 就求出了 9x + 30k = 3 的 (x,k) 一组解 (-3,1) 我们要求的是 9x' + 30k'' = 21 的一组解所以把 (-3, 1) 乘以 (21/3) = 7 所以 -21 就可以当 x_0 可以看看维基的资料，上面有很多种求法，例如递回的求法 ※ 引述《subgroup (紫裙子)》之铭言： : 最近刚开始学习mod : 看原文课本看不太懂 上网查了一下维基百科 : 上面写说 : 在数论中，线性同余方程是最基本的同余方程，「线性」表示方程的未知数次数是一次， : 即形如： : ax≡b (mod n)的方程。 : 此方程有解iff b 能够被 a 与 n 的最大公约数整除（记作 gcd(a,n) | b）。 : 这时，如果 Xo 是方程的一个解，那麽所有的解可以表示为： : {Xo + kn/d|k属於z} : 其中 d 是a与n的最大公约数。在模 n 的完全剩余系 {0,1,…,n-1} 中，恰有 d 个解。 : 我想请问一下那个"Xo"要怎麽找呢? : 是要一个一个带入找吗?? : 然後课本习题要我找的"incongruent solution"都恰好是我找的解耶 : 可是incongruent我查字典是"不一致的" : 怎麽互相矛盾呢@@? : 不好意思 问题看起来都很基本@@"但我就是不太懂欸><" : 谢谢大家 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 61.217.35.60 ※ 编辑: suhorng 来自: 61.217.35.60 (04/04 10:38)