用辗转相除法求出下列数的最大公约数第一个37585第二个390用辗转相除法求出下列数的最大公约数第一个37585第二个390455546第三个1734816343

Question

用辗转相除法求出下列数的最大公约数 第一个 375 85 第二个 390
用辗转相除法求出下列数的最大公约数
第一个 375 85
第二个 390 455 546
第三个 1734 816 343

Answer 1

两个整数的最大公约数是能够同时整除它们的最大的正整数.
辗转相除法基于如下原理：
两个整数的最大公约数等于其中较小的数和两数的差的最大公约数.例如,252和105的最大公约数是21（252 = 21 × 12；105 = 21 × 5）；因为252 − 105 = 147,所以147和105的最大公约数也是21.在这个过程中,较大的数缩小了,所以继续进行同样的计算可以不断缩小这两个数直至其中一个变成零.这时,所剩下的还没有变成零的数就是两数的最大公约数.由辗转相除法也可以推出,两数的最大公约数可以用两数的整数倍相加来表示,如21 = 5 × 105 + (−2) × 252.这个重要的等式叫做贝祖等式.