數論中關於”模同餘”的問題~

👨🏻‍🏫 學術台數學

[匿名]

2009-11-27 8:03 pm

最近在讀數論,但是模同餘這裡看不太懂,想請大家解答我的疑問~
1:解同餘方程求最小正整數解 13x&equiv;1(mod2436)

解答是:937
我知道此題即求13x+2436y=1 先利用歐基里得演算法得到 (937,-5)為
13x+2436y=1的一組解但是接下來我就不會算了

2:求89在mod233 的乘法反元素
解答是:144

請幫我解答以上2個問題~ 感謝~!

更新1:

第二題我求出來 (-89,34)為 89x+233y=1 的一組解所以89*(-89)=1(mod233) 可是解答是144 為什麼不是 -89 呢?

回答 (3)

myisland8132

2009-11-27 8:47 pm

✔ 最佳答案

第一題您已經計了答案。因為(x,y)=(937,-5)是一組解。13(937)+2436(-5)=1
13(937)=1+2436(5) 而2436(5) 被2436整除。所以此式即是13(937)=1 (mod 2436) 因此解答即是937

第二題同理 89=1 (mod 233) 等於求 89x+233y=1 的一組解。而反元素即是求出的x (對233同餘後)

👍 0 👎 0

[匿名]

2009-11-27 10:31 pm

Copestone 您好~ 我看過你的解答後有點疑問

求同餘方程之最小正整數解以 31x ≡ 1 (mod 4600) 此題為例
您算出的解為 x ≡ 2671 (mod 4600) 我的疑問是:可不可以將
答案寫成 x=2671 呢? x ≡ 2671 (mod 4600) 和 x=2671
這2種寫法是一樣的嗎? 謝謝~!

👍 0 👎 0

Copestone

2009-11-27 9:58 pm

請參考以下同類問題的詳細作法。如果你會歐幾里德的演算法，沒有理由不會求線性整數方程解的。你看你那一步不會，再細心體會。看意見欄也可以，寫法較明白。

http://tw.knowledge.yahoo.com/question/question?qid=1609102902543。

2009-11-27 15:05:00 補充：
最小正整數解只有一個 x = 2671。

寫成 x ≡ 2671 (mod 4600)，就代表所有的整數解了。

全看題目要求喔。上列網址那一題是找出所有整數解。

2009-11-27 15:09:44 補充：
-89 ≡ 144 (mod 233) 啊！！你沒解錯，答案也對，如果要求最小正整數，就是 144。

但如果是所有解，寫成 x ≡ -89 (mod 233) 也行。

👍 0 👎 0

收錄日期: 2021-04-26 13:50:05
原文連結 [永久失效]:
https://hk.answers.yahoo.com/question/index?qid=20091127000016KK02789

檢視 Wayback Machine 備份