作者huangwh (香腸)
看板Grad-ProbAsk
標題[理工] [離散] Modular multiplicative inverse
時間Thu Jul 22 01:21:45 2010
題型: Modular multiplicative inverse
模數乘法反元素
題目:
[定理證明] 假設a∈Z,n∈Z^+, 若gcd(a,n)=1, 則a在模n下的乘法反元素存在。
Pf: 因為gcd(a,n)=1 , 故∃s,t∈Z 使得 as+nt=1 | 1
=> as+nt≡1(mod n) | 2
因為nt≡0(mod n)，故as≡1(mod n) | 3
因此s是a在模n下的乘法反元素 | 4
以上是書上的證明
但我有一個地方卡住，以下使我的想法，不知道是否正確。
主要問題是在第二列，不太確定是怎樣換算出來的，下面是我的想法:
∵a=b+kn ↔ a≡b(mod n)
as+nt=1
=> a=as+nt
b=1
kn=0
=> as+nt≡1(mod n)
Q: 是這樣得到的嗎? 我總覺得怪怪的。
此外，在第三列部分，是因為題目欲求a在模n下的反元素m所以才會
ntnt≡0(mod n)，as≡1(mod n) 的吧???
麻煩大家
謝謝!
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.216.229.79
1F：→ doom8199:由<1>式知 as+nt=1 , 但原po中間的 "a=as+nt" 怎來的? 07/22 23:35
2F：→ huangwh:簡單來說 我是把as+nt看成個大項目"A" 再將其代入 07/23 00:25
3F：→ huangwh:a=b+kn ↔ a≡b(mod n) 中的a當中~~ 07/23 00:26
4F：→ huangwh:Q: 我只要想要問as+nt≡1(mod n)是由我上方的寫法 換算出 07/23 00:27
5F：→ huangwh:的嗎? 07/23 00:27
6F：推 doom8199:所以你是想證明 <1>式 嗎 @@? 07/23 00:31
7F：→ t3825288:第二列是根據歐幾里得演算法來的吧 07/23 21:58