辗转相除法求最大公因数例题讲解（用辗转相除法将两数的最大公因数表成两数的线性组合）

　　用“辗转相除法”将两数的最大公因数表成两数的线性组合

　　2019年8月22日星期四

　　本文接前文：

　　——《用现代数学方法解古题“物不知数”

一、平凡的开端：表达带余除法的小技巧

文中图片均来自网络

　　如果要做20除以6，小学二年级学生也会这样写：

　　20÷6＝3……2

　　只是我们有没有想过，省略号“……”到底算什么运算符？其实，它并不能具体表达和直接参与运算，这样的符号是会带来不便的。

　　更好的写法是这样的：

　　20＝6×3＋2

　　小学生其实也知道，这就是：被除数＝除数×商＋余数。

　　将其一般化，就是：

　　任给a、b∈Z，b≠0，存在唯一的一对q、r∈Z，使得：

　　a＝bq＋r，且0＜r＜｜b｜

　　是不是瞬间“高大上”了？是的。数学家还会死磕｛q，r｝的“存在性”和“唯一性”，并给出严密的逻辑证明。对此，我也是很“头疼”，以至于“深恶痛绝”的。来点经不起推敲的大白话，就是：

　　任意两个整数相除（除数不能为0），都存在唯一的商和余数，且余数小于除数。

　　或许，这体现了“人性化”。

二、峰回路转：“辗转相除法”横空出世

　　研究任意的整数对｛a，b｝，其中b≠0。

　　设另有整数对｛q，r｝，其中0＜r＜｜b｜，使得：

　　a＝bq＋r

　　（“人话”是：以a作被除数，b作除数，它们的商是q，余数是r）

　　另设：（a，b）＝d

　　（“人话”是：整数a和b的最大公因数是d）

　　万事俱备，只欠东风。下面来点小推理：

　　（a，b）＝d

　→d是a的因数，d是b的因数

　→d｜a，d｜b

　→d｜（bq＋r），d｜bq

　→d｜r

　→（b，r）＝d、（a，r）＝d、（a，b，r）＝d

　　这段写法不严谨：“推导出”的符号是双横线右箭头，形如“＝＝＞”，用“→”只是为了输入方便；推导过程较粗糙，公因数前冠以“最大”时，是需要另行证明的，这里只是为了突显思路，不是作教科书。

　　这说明（“人话”版）：

　　被除数和除数的公因数，是除数和余数的公因数，也是被除数的余数的公因数，更是被除数、除数、余数的公因数，最大公因数亦然。

　　这说明（“高级人话”版）：

　　求｛a，b｝的最大公因数，等价于求｛b，r｝的最大公因数，且这个步骤可以反复迭代使用。一般情况下，由于b＜a、r＜b，使得较大数对｛a，b｝变为较小数对｛b，r｝，问题得以简化。有限步后，必以可以整除的数对｛rn，r(n 1)｝结束。这就是“辗转相除法”的算理和由来。

　　（重要程度★★★★★）

　　举例说明：

　　求｛84，54｝的最大公因数。

　　①由于84＝54×1＋30，转而求｛54，30｝的最大公因数；

　　②由于54＝30×1＋24，转而求｛30，24｝的最大公因数；

　　③由于30＝24×1＋6，转而求｛24，6｝的最大公因数；

　　④由于24＝6×4＋0，即：6｜24，得：（24，6）＝6，也即：（30，24）＝6、（54，30）＝6、（84，54）＝6。

三、神奇的收获：最大公因数的线性表示

　　设：a、b、d∈Z，且（a，b）＝d

　　“线性”是说两个变量间的关系是一次函数关系。两个整数的最大公因数可以由两个整数线性表出，是指：

　　存在u、v∈Z，使得：d＝ua＋vb

　　（重磅！重磅！重磅！表达式“d＝ua＋vb”相较于“d＝（a，b）”，可以具体表达和直接参与运算喽！！！）

　　（重要程度★★★★★）

　　利用“辗转相除法”，不仅能求得这个“线性组合”的表达式，而且能证明这一事实。

　　以上文（84，54）＝6为例：

　　中间步骤有4个带余除法算式：

　　84＝54×1＋30

　　54＝30×1＋24

　　30＝24×1＋6

　　24＝6×4＋0

　　将前3个算式做一下变换得：

　　30＝84－54×1

　　24＝54－30×1

　　6＝30－24×1

　　倒推依次代入：

　　6＝30－24×1

　　＝30－（54－30×1）×1

　　＝－1×54＋2×30

　　＝－1×54＋2×（84－54×1）

　　＝2×84－3×54

　　于是有：u＝2、v＝－3。

四、后话

　　这部分是枯燥的，您必须拿起笔来演算下。

　　一些有趣的结论，恐怕也是诞生于枯燥的过程。总想着“有意思”，可能会让我们掉进坑里，从而发现不了大的“有意思”。

　　呵呵。

　　这样想吧：您现在拥有完全解决“物不知数”问题的方法了。

,