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

  2019年8月22日星期四

  本文接前文:

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

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

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

文中图片均来自网络

  如果要做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),都存在唯一的商和余数,且余数小于除数。

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

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

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

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

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

  研究任意的整数对{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。

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

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

  设: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。

四、后话

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

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

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

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

  呵呵。

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

,