在上篇文章《《几何原本》-第七卷初等数论（2）-命题1-如何快速判断两数是否互为素数？》的最后，我们留下一个问题：任意一组并非互为素数的数，无论这组数的位数有多大，有没有一种快速且准确的方法能够让我们求出它们的最大公约数？
另外在上篇文章中，我们运用第七卷命题1的方法快速验证了五组数是否互为素数。通过验证，我们发现其中的四组数互为素数，不过其中的第三组数261和762并非互为素数。
下面是上篇文章运用命题1的方法判断第三组数261和765是否互为素数的过程:
步骤①:762-261*2=240；
步骤②:261-240*1=21；
步骤③:240-21*11=9；
步骤④:21-9*2=3；
步骤⑤:9-3*3=0；
步骤⑥:因为通过上述步骤最后计算出来的余数为0，而非1，所以261与762并非互为素数。
不知道大家在看上文判断261和765是否互为素数的时候，是否也和我一样，总有一种感觉:步骤④中的余数3就是261与762的最大公约数，因为3能除尽步骤③中的余数9。
甚至我们可以大胆地猜想一下，任意两个并非互为素数的自然数，在使用类似上文判断261和765是否互为素数的方法的过程中，得出的最后那个能除尽余数的数，就是这两个数的最大公约数。
这种感觉就像哥德巴赫在1742年向欧拉提出的哥德巴赫猜想（任一大于2的整数都可写成三个质数之和）一样自然。
但是要证明我们的猜想，我们也一时半会想不到办法。
不过呢，欧几里得在《几何原本》第七卷初等数论命题2中，证明了我们的猜想是正确的。
下面让我们一起来看看命题2的证明过程：
已知条件:设AB、CD为已知的不互素的两个数。
目标：求AB、CD的最大公度数。
证明:
情形一：若CD可以量尽AB。
1、因为CD也可以量尽自身，所以CD是CD、AB的公度数。因为不存在可以量尽CD且大于CD的数，所以CD是CD、AB的最大公度数。
情形二：若CD无法量尽 AB。
2、因为CD无法量尽AB，所以AB、CD中的较大数不断地减去较小数，这样就有一个余数能量尽它前面一个数。这最后的余数不是一个单位，否则AB、CD是互素的两个数【第七卷 命题1】。
3、因此，某数将是量尽其前面的一个余数。
4、设以CD在BA上量出BE，余数为EA，EA小于CD；以EA在DC上量出DF,余数为小于EA的FC。
5、设CF可以量尽AE。因为CF可以量尽AE，AE可以量尽DF，所以CF也可以量尽DF。
6、又因为CF可以量尽其本身，所以CF可以量尽CD。因为CD可以量尽BE，所以CF可以量尽BE。
7、又因为CF可以量尽EA，所以CF也可以量尽BA。
8、因为CF可以量尽CD，所以CF可以量尽AB、CD。所以，CF是AB、CD的一个公度数。
9、可证CF是二者的最大公度数。若CF不是AB、CD的最大公度数，那么某个大于CF的数将可以量尽AB与CD。设这个数为G。
说明:这里使用反证法进行证明，首先假设与要证明的结论相对立的命题成立。
10、因为G可以量尽CD,CD可以量尽BE，所以G可以量尽BE。且G也可以量尽BA。因而，G也可以量尽余数AE。
11、因为AE可以量尽DF，所以G也可以量尽DF。又因为G可以量尽DC，所以G可以量尽CF，即较大数可以量尽较小数，这是不可能成立的。因此，大于CF的某数是无法量尽AB、CD的。
12、综上，CF是AB、CD的最大公度数。
以上是命题2的证明过程，通过证明，也说明我们前面的猜想是正确的，这也为我们求两数的最大公约数提供了一种高效且准确的方法。
在证明了命题2后，欧几里得随之就很自然地提出命题2的推论：
命题2的推论这里就无需再进行证明，下面我们运用命题2中的方法来快速求解两个并非互为素数的数间的最大公约数。
同样地，我们也提出五组数：
①4和6；
②24和84；
③270和630；
④1344和5680；
⑤12046和98770；
下面让我们一起感受命题2求解最大公约数这种方法的魅力：
1、求解第一组数4和6最大公约数的过程:
步骤①:6-4*1=2；
步骤②:4-2*2=0；
步骤③:因为通过上述步骤最后计算出来的余数为0，且最后一个数是被2整除的，所以2是4与6最大公约数。
2、求解第二组数24和84最大公约数的过程:
步骤①:84-24*3=12；
步骤②:24-12*2=0；
步骤③:因为通过上述步骤最后计算出来的余数为0，且最后一个数是被12整除的，所以12是24与84最大公约数。
3、求解第三组数270和630最大公约数的过程:
步骤①:630-270*2=90；
步骤②:270-90*3=0；
步骤③:因为通过上述步骤最后计算出来的余数为0，且最后一个数是被90整除的，所以90是270与630最大公约数。
4、求解第四组数1344和5680最大公约数的过程:
步骤①:5680-1344*4=304；
步骤②:1344-304*4=128；
步骤③304-128*2=48；
步骤④:128-48*2=32；
步骤⑤:48-32*1=16；
步骤⑥:32-16*2=0；
步骤⑦:因为通过上述步骤最后计算出来的余数为0，且最后一个数是被16整除的，所以16是1344与5680最大公约数。
5、求解第五组数12046和98770最大公约数的过程:
步骤①:98770-12046*8=2402；
步骤②:12046-2402*5=36；
步骤③2402-36*66=26；
步骤④:36-26*1=10；
步骤⑤:26-10*2=6；
步骤⑥:10-6*1=4；
步骤⑦:6-4*1=2；
步骤⑧:4-2*2=0；
步骤⑨:因为通过上述步骤最后计算出来的余数为0，且最后一个数是被2整除的，所以2是12046与98770最大公约数。
好了，这一讲就到这里了。
我是一个致力于科普数学、物理的科技媒体。想了解更多相关的知识，欢迎关注我的微信公众号科学发现之历程，期待你的到来。
