作者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