最大公因数的二三事
2018年7月22日星期日
五年级数学的“因数与倍数”及其后续知识，难煞许多小朋友。大抵除了态度、努力的差别，这部分内容概念众多、线索隐晦、与小朋友熟悉的生活问题联系匮乏，也是值得发掘的原因。抽象思维的特点就是运用概念进行思考、判断、推理。对此有困难的，说明您的思维正处于痛苦的转型期，熬过去，就会柳暗花明。当然，选择这个话题，也是我兴之所致，随性而为。希望对小朋友们有所帮助。
谈到“最大公因数”，您脑子里最先蹦出的是什么？
……
……
……
……
……
……
如果是“短除法”，说明您和我想到一块了。对此，您应当充满自信和欣慰。求最大公因数的方法正是今天话题的核心。首先让我们寻根溯源，找找“最大公因数”是哪根藤上结出的瓜。
回顾我们曾经做过的自然数的除法——大量地、不厌其烦的除法，您会认同以下的发现。当然，在此之前，我们最好先将0从自然数家族中剔除：0总是扮演“坏蛋”的角色——它不能做除数、不能做分母、不能做比的后项，不能做自然数的最高位，走到哪，就在哪“捣乱”；0混进自然数的家族，至今存在异议，许多数学“大牛”对此都持保留意见。但，最主要的是，我们已经不想和这个“坏蛋”纠缠太多。
自然数的除法分为三种情况：
1.商为整数无余数，如：6÷2＝3；
2.商为有限小数，如：10÷8＝1.25；
3.商为无限循环小数，如：1÷7＝0.142857 142857……。
显然，这是在将数系由自然数扩张到小数的情况下进行的讨论。所谓“自然数的除法”，我们只是对被除数、除数的约束，而非对其结果的限制。如果是那样，2、3应当合并为“有余数的除法”。
上述三种除法中，第1种是最漂亮的：被除数、除数、商都是自然数，且没有余数。如果除数和商还是一位数的话，就是我们最喜欢的“表内乘除法”。对这种漂亮的除法，我们起个名字叫做“整除”。在整除这条“根”上，将生长出“因数与倍数”等一系列茁壮的茎和丰硕的果实。如果您在学习上也不“忘本”的话，您也会是一个让人尊重的人。
整除“妈妈”生了两个孩子：因数和倍数。6÷2＝3，我们说：6被2整除，或2整除6；我们定义：6是2的倍数，2是6的因数。因数和倍数就像“爸爸”、“妈妈”、“儿子”、“女儿”……这些概念一样，表示的是一种关系，而非具体事物的名称。“甲是爸爸”与“6是倍数”的错误是一样的，应当说“甲是谁的爸爸”、“6是谁的倍数”。您能理解的是：没人敢给自己取名叫做“爸爸”。
从此，“因数”与“倍数”蓬勃发展，衍生出了许许多多“悲壮”的东西。我们略用一张图示，傲视它们，寻找一种“弹指间灰飞烟灭”的虚妄感觉。
深入认识自然数，为分数四则运算奠定基础，是这部分知识重要的目的和归宿。“公因数”所以多了一个“公”字，是因为研究角度的变化：由寻找一个自然数的因数变化为寻找两个或更多的自然数的相同的因数。“最大”公因数说明，在一众“公因数”中，鹤立鸡群的“老大”才是最突出的、最有意义的。求取两个或多个自然数的最大公因数，基于这些原生概念，又有新的思维方法。不要过分自恋于已经知道的知识和掌握的方法，在我们的思维还没有提升到新的层次时，我们无法准确、全面、深入地了解自己的幼稚。这句话或将成为您阅读本文最大的收获。
以下的做法，目的在于“删繁就简，抓主要矛盾”。
（一）符号约定。8和12的最大公因数，记为：（8，12）＝4；最小公倍数记为：［8，12］＝24。一个用圆括号，一个用方括号，数字间以逗号隔开。计算机的世界里又有以下表示：最大公因数：gcd（8，12）＝4，最小公倍数：lcm（8，12）＝24。“gcd、lcm”分别是英文“最大公因数、最小公倍数”的单词的首字母，计算机里以其为函数名或命令名。
（二）情况简化。求多个自然数的最大公因数或最小公倍数的问题都可以转化为求两个自然数的gcd或lcm。例如：
（8，12，16）＝（（8，12），16）＝（4，16）＝4
［8，12，16］＝［［8，12］，16］＝［24，16］＝48
您看明白其中化归的思路了吗？如果要求3个自然数a、b、c的最大公因数（最小公倍数同），我们可以先随便拿出其中两个数求取最大公因数g1，然后再用g1与第三个数再次求取最大公因数，设为g，就是这3个自然数的最大公因数。
（a，b，c）＝（（a，b），c）＝（a，（b，c））＝（（a，c），b）
（a，b，c）＝（（a，b），c）＝（g1，c）＝g
因此，我们只需重点讨论如何求取两个自然数的最大公因数就可以了，拓展时要做的就是：再来一遍、再来一遍、再来一遍……
方法一：列举法
有时，我不认为这是求最大公因数的方法，它是用来阐释概念的。
（8，12）＝？
①列举8的所有因数：1、2、4、8；
②列举12的所有因数：1、2、3、4、6、12；
③列举公因数：1、2、4；
④找出最大公因数：4。
（8，12）＝4。
仅此一例，聪明的您便会理解一系列概念。
方法二：短除法
下图是人教版五年级《数学》下册56页、61页的课外知识介绍：
显然，这是重要的，老师们会将其重新搬回课堂。此处不再赘述。我们将重点放在“短除法”的理解上。
对比一下除法竖式和短除号：
短除号其实是竖式除号的颠倒，除数依旧在左边，被除数依旧在里面，商从上面移到下面。我曾想：这个除法哪“短”呢？聪明的您是否找到了线索：正常的竖式除法要经历试商、乘积、求差、比较余数和除数4个小步骤，“短除法”省略了后面3个步骤，是一种直接写商的除法。这岂止是“短”了，那是“相当的短”了！为何如此？因为短除法的特点在于除法的继续施加，可以循环往下，重复第二次、第三次……上一步的商旋即变为下一步的被除数，如果将这个过程用普通除法竖式表达出来，会写啰嗦的一大堆，如下图：
简便是短除法的优点，但也有代价。如果被除数很大，心算弱的小朋友估计得借助于普通除法竖式另行求商。相信，您会对此感同身受。
利用短除法求取两个自然数的最大公因数，其实质是对这两个自然数作质因数分解，而且首先罗列相同的质因数。教材61页示例：（24，36）＝12的计算过程，同以下：
24＝（2×2×3）×2
36＝（2×2×3）×3
质因数分解是具有“标准形式”的，比如：将质因数从小到大排列，以幂次方乘积的形式表达（以后有工夫了，详细讨论）。利用短除法求最大公因数，打乱了这种标准形式：它将两个自然数相同的质因数排在前面，不同的质因数过滤在后。这种“相同”是建立在一一对应的基础上的，能够对应的最大部分的乘积即为两个自然数的gcd。
掌握这种方法会让小学时期的我们自信满满、神采奕奕。
方法三：辗转相除法
这个方法其实是我国古代“更相减损术”的小升级，如图：
如果上面的话让您感到费解，是因为您没有拿起纸和笔举例子。（77，21）＝？我们智慧的古人依靠一串减法就求出了结果：
77－21＝56
56－21＝35
35－21＝14
21－14＝7
14－7＝7
当差等于减数时，这个“等数”7就是77和21的最大公因数。您是否有点惊讶、不习惯、反感？它始终在遵循“大减小”的规则，写成分数的形式或许更好一点：
然而更为简便的是古希腊数学家欧几里得发明的“辗转相除法”，原因只是：连续施加多次的减法，可以用除法一步到位！上例变为：
77÷21＝3……14
21÷14＝1……7
14÷7＝2……0
余数为0时停止，最后一步的除数即为两数的最大公因数。
请注意，“辗转”的具体意思是：上一步的除数变为下一步的被除数，上一步的余数变为下一步的除数，反复施加直至整除，取最后一步的除数作为结果。再看一例：
（72072，100548）＝？
①100548÷72072＝1……28476
②72072÷28476＝2……15120
③28476÷15120＝1……13356
④15120÷13356＝1……1764
⑤13356÷1764＝7……1008
⑥1764÷1008＝1……756
⑦1008÷756＝1……252
⑧756÷252＝3
（72072，100548）＝252
您可以用“短除法”对比一下。或许，您并不觉得“辗转相除法”是优秀的方法，我也可以明确的声明：本文并不打算教会小朋友这些。但我想说明的是：好坏的评判取决于面对的问题情境。一个大数的质因数分解，甚至判断这个大数是不是质数，是一个被称做“np难题”的东西，简言之，就是计算机也无法在确定、已知、有限的时间内完成。譬如我们要判断397是不是质数，最笨、最暴力的方法是让计算机逐个检验2～396，在这种情况下：
1位数，检测10次左右；
2位数，检测10×10次左右；
3位数，检测10×10×10次左右；
……
这种困难度是以指数级增加的，理论数学的世界里，10000位长度的数字也是微不足道的。
您也许已经感受到了算法的重要，好的算法已经演化为当今世界的“核心竞争力”，这个意识小朋友应当要有的，就好比“数学王子”高斯在小时候做“1＋2＋3＋……＋99＋100”时用到的方法那样。“质数判断”于本文是节外生枝，那扇门的背后，全是拼尽智商的东西，似我等，唯一的收获就是证明自己的“平凡”。希望存在于一代代“天才”的小朋友们身上。如果您进入计算机的世界——您一定会进入——可以提前有所认识的。对于求最大公因数，如果用“列举法”、“短除法”的思路编写能够让计算机执行的代码，“小白”如我，是会感到茫然和束手无策的。然而用“辗转相除法”的算法思路写出的代码，却只需10行左右就够了。到那时，您会真正发现“算法”的神奇！
有好奇与探索相伴的人生是精彩的，就好比旅行途中发现别样的风景一样。
再会。
,
