通过本文主要向大家介绍了扩展欧几里德算法,欧几里德算法,欧几里德算法求逆元,欧几里德算法流程图,欧几里德算法c等相关知识,希望对您有所帮助,也希望大家支持linkedu.com www.linkedu.com
欧几里德算法称为辗转相除法，用来求已知m、n两个自然数的公因数。结合程序说明一下辗转相除的具体情况。
首先看递归实现：
1、对输入的两个自然数m > n取余数r，使得0<= r < n
2、如果r为0，n即为所求结果，直接返回
3、r不为0，则赋值m=n,n=r从步骤1开始重新执行
两自然数的公因数的定义说明了计算结果产生的条件。如果步骤1中计算出的余数r = 0，则较小的数为公因数。如果r!=0则自然数m、n的关系可表示为：m = kn + r（其中k为自然数），等式可以证明能整除m的任何数必定能整除n和r；等式进一步可变形为：r = m - kn，说明同时整除m、n的任何数也必定能整除r。也就是说，能整除m、n的数的集合与整除n、r的数的集合相等。所以辗转相除的方法成立。
再发布一个循环实现欧几里德算法的版本。
</div>