辗转相除法是什么？

辗转相除法，即欧几里德算法，是一种简洁有效的方法，用于求解两个或多个正整数的最大公约数。其核心原理是通过不断重复的除法和取余操作来逼近最大公约数。具体步骤如下：首先，用较大的数除以较小的数，得到余数（第一余数）；然后用这个余数去除除数，又会产生一个新的余数（第二余数），如此循环，直到余数为零。这个非零余数就是前一步的除数，即为两个数的最大公约数。当余数为零时，最后一次的除数即为最大公约数，与更相减损法有所不同。

这个算法的理论基础建立在两个重要性质上：一是如果 r 是 a 除以 b 的余数，那么 a 和 b 的最大公约数等于 b 和 r 的最大公约数；二是任何数与其倍数的最大公约数一定是该数本身。可以这样表述：首先，a 除以 b，得到余数 r（0≤r

了解了辗转相除法，我们就能有效地解决关于最大公约数的计算问题。这个方法在数学和计算机科学中广泛应用，尤其是在算法设计和密码学等领域。