视频字幕
最大公约数,简称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)。这个算法在数论、密码学等领域都有重要应用。掌握辗转相除法有助于我们解决实际的数学问题。