用“辗转相除法”将两数的最大公因数表成两数的线性组合
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。
四、后话
这部分是枯燥的,您必须拿起笔来演算下。
一些有趣的结论,恐怕也是诞生于枯燥的过程。总想着“有意思”,可能会让我们掉进坑里,从而发现不了大的“有意思”。
呵呵。
这样想吧:您现在拥有完全解决“物不知数”问题的方法了。
,