互素(互素是什么意思)

这是数论入门系列文章，旨在普及数学知识，拓展读者的数学思维。为什么用图片和文字代替视频？图形有三个优点:一是图形数据量小，节省学习时间；第二，有助于个人积极思考；第三，文中的关键词可以方便读者获取相关信息。

我们在毕达哥拉斯数列的研究中看到，整除和因式分解的概念是数论的重要工具。在本章中，我们将进一步研究这些观点。

假设m和n是整数。n除以m意味着n是m的倍数，也就是有一个整数k使得n = MK .如果m整除n，我们就记为m i n .同理，如果m不能被n整除，就记为。

比如因为、、、、。6的因数是1，2，3。另一方面，由于没有5的倍数等于7，所以。

一个数除以n叫做n的因数。

如果两个整数已知，就可以求出它们的公因数，也就是把它们整除的数。例如，由于and，4是12和20的公因数。注意，4是12和20的最大公因数。同样，3是18和30的公因数，但不是最大的，因为6也是公因数。两个数的最大公因式经常出现在我们的数论讨论中，是一个极其重要的量。

两个数A和B的最大公因数(不全为零)是将它们整除的最大数，记为gcd(a，B)。如果gcd(a，b) =1，我们称A和6互质。

在前面的两个例子中，

Gcd(12，20) = 4，gcd (18，30) = 6。

另一个例子是

gcd(225，120) = 15。

通过分解因子和，可以验证答案是正确的，但一般来说，分解A和B并不是计算A和B的最大公因式的有效方法。

求两个数的最大公因式最有效的方法是欧几里德算法，它由一系列带余数的除法组成，直到余数为零。在描述一般方法之前，我们用两个例子来说明。

作为第一个例子，我们计算gcd(36，132)。第一步是将132除以36，得到商3和余数24。让我们把它写成

132 = 3 x 36 + 24。

第二步是取36，用36除以上一步的余数24。

36 = 1 x 24 + 12。

接下来，用24除以12得到余数0，

24 = 2 x 12 +0。

欧几里德算法表明，当求余数0时，上一步的余数就是前两个数的最大公因式。所以在这种情况下，我们发现gcd(132，36) =12。

我们举一个更大的例子来计算一下

gcd(1160718174，316258250).

这个大数的例子是为了说明欧几里德计算最大公因式的算法远比因式分解有效。从1160718174除以316258250开始，得到商3和余数211943424。接下来，取316258250，用211943424去掉，继续这个过程，直到得到余数0。具体计算见下表:

1160718174 = 3 x 316258250+211943424

316258250 = 1 x 211943424+104314826

211943424 = 2 x 104314826 + 3313772

104314826 = 31 x 3313772 + 1587894

3313772 = 2 x 1587894 + 137984

1587894 = 11 x 137984 + 70070

137984 = 1 x 70070 + 67914

70070 = 1 x 67914 + 2156

67914 = '3x2156+| 1078 |最大公因数

2156 = 2 x 1078 +0

注意每一步如何将A除以B得到商Q和余数r .换句话说，

A= Q x B+ R。

然后在下一步，用数字B和R代替原来的A和B，继续这个过程，直到余数为0。此时，上一步的余数r就是前两个数的最大公因式。因此，上述计算表明

gcd(1160718174，316258250) = 1078。

通过验证1078确实是一个公因数，我们可以部分地测试我们的计算(一个好主意)。事实上，

1160718174 = 1078 x 1076733，316258250 = 1078 x 293375。

我们来分析一下欧几里德的算法。对于一般情况，有

如果是这样，每一行看起来就像。

。

为什么最后一个非零余数R是A和B的公因数？让我们从底线开始向上努力。最后一行，表示整除。然后是上一行

表示可除性，因为它能被整除。现在看前面一行，我们已经知道了分部和分部，所以我们也知道分部。逐行上移。到了第二行，我们已经知道了划分和划分。所以第二行表示B是可整除的。最后到达顶行，利用可整除b可以得到可整除A的结论，这就完成了最后非零余数是A和b的公因数的证明。

但为什么是A和B的最大公约数呢？假设D是A和B的任意公因数，让我们回到方程表。将A和B从第一个方程和D中均分，可以得到D也是可整除的。那么第二个等式表明d是可整除的。逐行继续。在每一步，我们得到前两个余数的和除以D，然后我们可以知道D也除以下一个余数。最后到达倒数第二行，至此得出D整除的结论。因此，我们证明了如果D是A和B的任意公因数，那么D是可整除的。所以一定是A和b的最大公约数。

综上所述，我们验证欧几里德的算法确实计算出了最大公因式，其重要性使得有必要形成一个定理。

定理5.1(欧几里德算法)计算两个整数A和B的最大公因数shilling然后计算相继的商和余数。

直到某个余数为0。的最后一个非零余数是A和b的最大公因数。

为什么欧几里德的算法总能完成任务？换句话说，我们知道最后一个非零余数是期望的最大公因式，但为什么一定要得到真正等于0的余数呢？这不是一个无聊的问题，因为很容易给出一个没有终止性的算法；甚至有一个简单的算法，所以人们不知道它是否会被终止。幸运的是，很容易看出欧几里德算法总是终止的，原因很简单，每次计算商和余数时，

A= Q x B+ R，

余数在0和B-1之间。这是显而易见的，因为如果是这样，你可以在商Q上再加1，然后从r上减去B，所以，欧几里德算法中的余数一直在减少:

但是所有余数都大于等于0，所以得到一个严格递减的非负整数序列。最后，必须达到等于0的余数；事实上，很明显，余数0将在最多6步后获得。幸运的是，欧几里德的算法远比这有效。欧几里德算法的步骤数最多是B的7倍，所以在计算机上，当A和B之间有几百甚至几千比特时，很容易计算出gcd(a，B)。

综上所述，在欧几里德算法中，有几个概念是我们需要理解的:

证明最大公约数时，分了两步，先证明是公约数，再证明是最大的公约数。这里利用了一个包含的概念，最大公约数首先是公约数。欧几里得算法的可停止性，如果算法不能停止，或不能快速停止，也不是一个好的算法。