这是一道数学证明题，和扩充的欧几里得算法有关
如果n和m为互素，则存在一个整数n'使得nn'≡1 ( modulo m ) 。利用扩充的欧几里得算法证明这一点乖乖 欧几里得扩充的算法我都看不懂。。
更不说证明了。。。
modulo 是同余的符号。
麻烦大家了哈
谢谢啦 这个是显而易见的 nn'实际上是满足：
1、是n的倍数
2、除以m余1
的最小数字，根据剩余定理，这样的数一定存在 楼上的可以给我讲讲扩充的欧几里得算法不？？
我看了半天没看出来 它和没扩充之间的有什么不一样
不理解 如果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可以为负 那么根据这个方法，如果n和m为互素，则GCD(m,n)=1，存在两个整数x,y，满足：xn+ym=1
只有证明y为负数，x为整数就可以了 假设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 楼主，用扩展欧几里得算法干嘛，用欧拉函数好像就能证了
页:
[1]