辗转相除法

辗转相除法

‌辗转相除法计算公式辗转相除法（又称欧几里得算法）的计算公式为：gcd(a,b) = gcd(b,a mod b)。其中，gcd表示最大公约数，mod表示取余操作。‌应用领域辗转相除法主要应用在数学和计算机两个领域。在数学中，它用于求解两个非负整数的最大公约数；在计算机科学中，它常用于算法设计和优化，如密码学、数论算法等。原理辗转相除法的原理基于一个数学定理：两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数。通过不断将较大的数除以较小的数并取余，然后更新除数和余数，直到余数为0，此时除数即为两数的最大公约数。‌证明辗转相除法的证明基于整除的性质和最大公约数的定义。假设a和b是两个非负整数，且a>b。设d是a和b的公约数，那么d可以整除a和b。由于a=bq+r（其中q是商，r是余数），因此d也可以整除r（因为d可以整除a和b，所以d可以整除a-bq，即r）。因此，d也是b和r的公约数。反过来，如果d是b和r的公约数，那么d也可以整除a（因为d可以整除b和r，所以d可以整除bq+r，即a）。因此，a和b的公约数与b和r的公约数是相同的，其最大公约数当然也相同。‌示例以求288和123的最大公约数为例，操作如下：用288除以123，得到余数165。用123除以165，得到余数62。用165除以62，得到余数41。用62除以41，得到余数21。用41除以21，得到余数20。用21除以20，得到余数1。用20除以1，得到余数0。此时，余数为0，所以1是288和123的最大公约数。