辗转相除法是欧几里德提出的。
辗转相除法， 又名欧几里德算法（Euclidean algorithm），是求两个正整数之最大公约数的算法。它是已知最古老的算法， 其可追溯至公元前300年前。
它的具体做法是：用较大数除以较小数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。
如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。 另一种求两数的最大公约数的方法是更相减损法。
《九章算术》第一篇《方田》记载了类似此法的求两正整数最大公约数及最简分数的方法：约分术曰：可半者半之，不可半者，副置分母子之数，以少减多，更相减损，求其等也。
辗转相除法即是针对两数相差较大的情况而做的改善，将过程中减法灵活的改变为除法，减小计算量，但实际上两个方法的本质是相同的，都是为了在数字位数较多时以最简方法求出最大公约数，因此也被我国古代科学家推广用于求最小公倍数。
内容全部来源于网络收集，如有侵权，请联系网站删除！
QQ：24596024