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

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<b)
然后如果r0不是0,那么我们用b代替a,用r0代替b,然后继续上面的过程,知道r0=0,那么b就是结果d了.
而扩充的算法除了求得d以外,还希望能够得到x0,y0,使得x0*a+y0*b=d
假设上面计算过程得出中间结果是:
a=u1*b+r0
b=u2*r0+r1
r0=u3*r1+d
那么通过上面的结果,我们首先可以得出
d=r0-u3*r1
然后替换r1,得到
d=r0-u3*(b-u2*r0)=(1+u3*u2)*r0-u3*b
然后再通过第一式替换r0,得到
d=(1+u3*u2)*(a-u1*b)-u3*b=(1+u3*u2)*a-(u1+u1*u2*u3+u3)b

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

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

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

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

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。