欧几里德算法证明得算法证明有个地方不清楚

点击联系发帖人 时间：2018-10-17 14:48

欧几里德算法证明

根据逆元的定义则可以转化为a*x+b*y=1。这样就可以用扩展欧几里德算法证明得算法求x了

注意：在gcd不为1说明逆元不存在（因为c=1，c%gcd==0为有整数解的充分必要条件）若为1,调整x0到0~m-1的范围中即可

}

证明：定理：两个整数的最大公約数等于其中较小的那个数和两数相除余数的最大公约数（Greatest Common Divisor）缩写为GCD。

假设d是a,b的一个记作d|a,d|b，即a和b都可以被d整除

进而d|a.因此d也是a,b的公约數

因此(a,b)和(b,a mod b)的公约数是一样的，其最大公约数也必然相等得证。

}