
一般针对两个数,例如求164和296的最大公约数,辗转相除法:296=1*164+132,164=1*132+32,132=4*32+4,32=8*4,所以164和296的最大公约数为4。
辗转相减法是一种求两个数的最大公约数(Greatest Common Divisor,简称 GCD)的方法。其基本原理是,用大的数去减小的数,然后再用减数去减余数,如此反复,直到余数为 0。最后一步的被减数就是最大公约数。
以下是一个使用辗转相减法求两个数的最大公约数的例题:
例如要求 18 和 24 的最大公约数:
Step 1:用大数减小数:24 - 18 = 6。
Step 2:用小数减余数:18 - 6 = 12。
Step 3:用大数减余数:12 - 6 = 6。
Step 4:用小数减余数:6 - 6 = 0。
Step 5:所以最大公约数为 6。
另外,如果两个数相等,那么它们的最大公约数就是它们本身。