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)