Re: [理工] 中國剩餘定理除數有公因數
※ 引述《sandybright (情執)》之銘言：
: x = 3 mod 10
: x = 5 mod 94
: 請問如果是這樣該怎麼算呢？
: 謝謝
因為10跟94不互質
所以要拆開
x≡3 mod 10
x≡5 mod 94
=>
x≡1 (mod 2)
x≡3 (mod 5)
x≡5 (mod 47)
接下來就分別找 5*47*a ≡ 1 (mod 2) => a=1
2*47*b ≡ 1 (mod 5) => b=4
2*5*c ≡ 1 (mod 47) => c = 33
=> x = 1*5*47*1 + 3*2*47*4 + 5*2*5*33 = 3013
3013 ≡ 193 (mod 470)
=> x = 193+470k (k∈Z)
#
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.112.83.234
推
11/06 21:48, , 1F
11/06 21:48, 1F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：