这是一系列关于数论的介绍性文章，目的在于推广数学知识，拓展读者的数学思维至于为什么用图文而不是视频？图文有三个优越性：一是图文数据量小，节省学习时间；二是有助于个人主动思考；三是文字里的关键字，可以方便读者查阅相关资料，接下来我们就来聊聊关于最小公约数和最大公约数定义?以下内容大家不妨参考一二希望能帮到您!
最小公约数和最大公约数定义
这是一系列关于数论的介绍性文章，目的在于推广数学知识，拓展读者的数学思维。至于为什么用图文而不是视频？图文有三个优越性：一是图文数据量小，节省学习时间；二是有助于个人主动思考；三是文字里的关键字，可以方便读者查阅相关资料。
我们在勾股数组的研究中已经看到，整除性与因数分解的概念是数论的重要工具。在本章中我们来更进一步地考察这些想法。
假设m与n是整数，。 m整除n指n是m的倍数，即存在整数k使得n=mk。如果m整除n，我们记为m I n。类似地，如果m不整除n，则记为。
例如,由于，，所以, 。 6的因数是1，2，3。另一方面，由于没有5的倍数等于7，所以。
整除n的数称为n的因数。
如果已知两个整数，我们可以求其公因数，即整除它们两个的数。例如,由于且，所以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，用前一步的余数24除36得
36 = 1 x 24 12.
下一步,用12除24求得余数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 = '31 x 2156 |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的任意公因数，让我们回到等式表。从第一个等式和d整除a与b，可得d也整除。则第二个等式表明d一定整除。逐行继续下去，在每一步我们得到d整除前两个余数与，则前行可知d也整除下一个余数。最终到达倒数第二行，至此就得到d整除的结论。因此我们已证明如果d是a和b的任意公因数， 则d整除。于是， 一定是a与b的最大公因数。
综上所述，我们验证了欧几里得算法的确算出了最大公因数，它的重要性使得有必要把它形成一个定理。
定理5.1(欧几里得算法) 要计算两个整数a与b的最大公因数，先令且，然后计算相继的商和余数
直到某余数为0。最后的非零余数就是a与b的最大公因数。
为什么欧几里得算法总能完成任务呢？换句话说，我们知道最后的非零余数就是所希望的最大公因数，但是为什么一定会得到确实等于0的余数呢？这并不是一个无聊的问题，因为容易给出不终止的算法；甚至存在着很简单的算法，使得人们不知道它是否会终止。幸运的是，容易看出欧几里得算法总会终止，理由很简单，每次计算商和余数，
A= Q x B R，
余数在0与B-1之间。这是显然的，因为如果，则可以再加1到商Q，并从R减去B。所以，欧几里得算法中的余数不断减小：
但是，所有余数大于等于0，因此得到非负整数的严格递减序列。最后必然达到等于0的余数；事实上，显然至多经过6步就会得到余数0。幸运的是，欧几里得算法远比这更有效。欧几里得算法的步数至多是b的位数的7倍。所以，在计算机上当a与b有几百位甚至几千位时，很容易计算 gcd(a, b)。
总结，在欧几里得算法里，有几个概念需要我们理解：
- 证明最大公约数时，分了两步，先证明是公约数，再证明是最大的公约数。这里利用了一个包含的概念，最大公约数首先是公约数。
- 欧几里得算法的可停止性，如果算法不能停止，或不能快速停止，也不是一个好的算法。
