[理工] [離散] Modular multiplicative inverse
題型: 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
→
07/22 23:35, , 1F
07/22 23:35, 1F
→
07/23 00:25, , 2F
07/23 00:25, 2F
→
07/23 00:26, , 3F
07/23 00:26, 3F
→
07/23 00:27, , 4F
07/23 00:27, 4F
→
07/23 00:27, , 5F
07/23 00:27, 5F
推
07/23 00:31, , 6F
07/23 00:31, 6F
→
07/23 21:58, , 7F
07/23 21:58, 7F