这是一道数学证明题，和扩充的欧几里得算法有关

budong · 发表于 2009-8-3 22:25:22

您需要登录才可以下载或查看，没有账号？欢迎注册

×

如果n和m为互素，则存在一个整数n'使得nn'≡1 ( modulo m ) 。利用扩充的欧几里得算法证明这一点乖乖欧几里得扩充的算法我都看不懂。。更不说证明了。。。 modulo 是同余的符号。麻烦大家了哈谢谢啦

282842712474 · 发表于 2009-8-4 08:30:07

这个是显而易见的

282842712474 · 发表于 2009-8-4 08:42:33

nn'实际上是满足： 1、是n的倍数 2、除以m余1 的最小数字，根据剩余定理，这样的数一定存在

budong · 发表于 2009-8-4 23:08:53

楼上的可以给我讲讲扩充的欧几里得算法不？？我看了半天没看出来它和没扩充之间的有什么不一样不理解

282842712474 · 发表于 2009-8-5 08:01:25

如果gcd(a,b)=d，则存在m,n，使得d = ma + nb，称呼这种关系为a、b组合整数d，m，n称为组合系数。当d=1时，有 ma + nb = 1 ，此时可以看出m是a模b的乘法逆元，n是b模a的乘法逆元。这里的n、m可以为负

282842712474 · 发表于 2009-8-5 08:04:22

那么根据这个方法，如果n和m为互素，则GCD(m,n)=1，存在两个整数x,y，满足：xn+ym=1 只有证明y为负数，x为整数就可以了

mathe · 发表于 2009-8-5 08:18:44

假设gcd(a,b)=d 计算方法如下,设 a=u*b+r0 (0<=r0

manthanein · 发表于 2017-1-21 22:23:42

楼主，用扩展欧几里得算法干嘛，用欧拉函数好像就能证了

账号		自动登录	找回密码
密码			欢迎注册

[提问] 这是一道数学证明题，和扩充的欧几里得算法有关