视频字幕
最大公约数，简称GCD，是两个或多个整数共有约数中最大的正整数。让我们通过一个例子来理解。12的约数有1、2、3、4、6、12，18的约数有1、2、3、6、9、18。它们的公约数是1、2、3、6，其中最大的是6，所以12和18的最大公约数是6。
辗转相除法，也叫欧几里得算法，是求最大公约数的高效方法。它的原理是：两个正整数a和b的最大公约数，等于b和a除以b的余数的最大公约数。让我们用98和56来演示：98除以56等于1余42，然后56除以42等于1余14，最后42除以14等于3余0。当余数为0时，最后的除数14就是98和56的最大公约数。
现在让我们逐步演示求48和18的最大公约数。第一步：48除以18等于2余12，所以GCD(48, 18)等于GCD(18, 12)。第二步：18除以12等于1余6，所以GCD(18, 12)等于GCD(12, 6)。第三步：12除以6等于2余0，当余数为0时，最后的除数6就是答案。因此GCD(48, 18)等于6。
最大公约数有几个重要性质。第一，最大公约数满足交换律，GCD(a, b)等于GCD(b, a)。第二，任何数与0的最大公约数等于这个数本身。第三，如果d是a和b的公约数，那么d也一定是它们最大公约数的约数。第四，对于正整数k，GCD(ka, kb)等于k乘以GCD(a, b)。这些性质在数学证明和算法优化中都非常有用。
让我们总结一下今天学习的内容。最大公约数是两个或多个整数共有约数中最大的正整数。辗转相除法是求最大公约数的高效算法，其原理是GCD(a, b)等于GCD(b, a mod b)。这个算法在数论、密码学等领域都有重要应用。掌握辗转相除法有助于我们解决实际的数学问题。