辗转相除法的原理

变质感情 3个月前已收到2个回答举报

共回答了30个问题采纳率：97.9% 评论

欧几里德算法又称辗转相除法，是指用于计算两个非负整数a，b的最大公约数。应用领域有数学和计算机两个方面。计算公式gcd(a,b) = gcd(b,a mod b)。

其计算原理依赖于下面的定理：两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。最大公约数（Greatest Common Divisor）缩写为GCD。gcd(a,b) = gcd(b,a mod b) (不妨设a>b 且r=a mod b ,r不为0)

21小时前

共回答了283个问题评论

答：辗转相除法的原理是，两个整数的最大公约数等于其中较小的数和两数的相除余数的最大公约数。

补充内容：

辗转相除法，又名欧几里德算法乃求两个正整数之最大公因子的算法，它是已知最古老的算法，其可追溯至公元前300年前。

辗转相除法处理大数时非常高效，它需要的步骤不会超过较小数的位数的五倍，加百利拉梅于1844年证明了这点，开创了计算复杂性理论。

辗转相除法可以求出特定条件的不定方程的一组整数解，两个整数的最大公约数是能够同时整除它们的最大的正整数

19小时前

可能相似的问题

猜你喜欢的问题

热门问题推荐