欧几里德算法，又称滚动除法，用于计算两个整数a和b的最大公约数，其计算原理取决于以下定理：定理：gcd（a，b）=gcd（b，amodb）证明：a可以表示为a=kbr，则r=amodb，假设d是a，b的公约数，则d|a，d|b，r=a-kb，所以d|r，所以d是（b，amodb）的约定数，假设d是（b，amodb）的公约数，那么d|b，d|r，但是a=kbr，所以d也是（a，b）的公约数。因此，（a，b）和（b，a，mod，b）的公约数是相同的，它们的最大公约数必须相等
欧几里得算法原理欧几里得算法推导欧几里德算法例题
微信 分享
