數學知識交流---模運算 (2)

(1) 301x ≡ 781 (mod 1798), x = ?
解：
301x ≡ 781 (mod 1798) -(1)
1798x ≡ 0 (mod 1798) --(2)
(1)×6 - (2)，得：
8x ≡ 4686 (mod 1798)
8x ≡ 1090 (mod 1798) --(3)
(3)×225 - (2)，得：
2x ≡ 245250 (mod 1798)
2x ≡ 722 (mod 1798) ---(4)
(4)×151 - (1)，得：
x ≡ 108241 (mod 1798)
x ≡ 361 (mod 1798)

(2) 273x ≡ 342 (mod 573), x = ?
解：
273x ≡ 342 (mod 573)
273x ≡ 342 (mod 191)
91x ≡ 114 (mod 191) ---(1)
191x ≡ 0 (mod 191) ----(2)
(2) - (1)×2，得：
9x ≡ -228 (mod 191)
9x ≡ 154 (mod 191) ----(3)
(1) - (3)×10，得：
x ≡ -1426 (mod 191)
x ≡ 102 (mod 191)

2011-08-03 17:05:00 補充：
疑難解答：
1. 為何 273x ≡ 342 (mod 573) 會變成 273x ≡ 342 (mod 191)？
可參考http://zh.wikipedia.org/zh-tw/%E5%90%8C%E9%A4%98
中的性質4(第一條式)：a ≡ b (mod cn) ==> a ≡ b (mod n)
2. 為何 273x ≡ 342 (mod 191) 會變成 91x ≡ 114 (mod 191)？
可參考相同網頁中的性質4(第三條式)：
ac ≡ bc (mod m) 且(c, m) = 1 ==> a ≡ b (mod m)

(1) x = 361
(2) x = 191n + 102