Re: [數論] 關於mod的問題
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)
→
04/04 12:16, , 1F
04/04 12:16, 1F
推
04/04 15:14, , 2F
04/04 15:14, 2F
討論串 (同標題文章)