最大公因數的二三事

　　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頁的課外知識介紹：

人教五數下冊56頁

人教五數下冊61頁

　　顯然，這是重要的，老師們會将其重新搬回課堂。此處不再贅述。我們将重點放在“短除法”的理解上。

　　對比一下除法豎式和短除号：

　　短除号其實是豎式除号的颠倒，除數依舊在左邊，被除數依舊在裡面，商從上面移到下面。我曾想：這個除法哪“短”呢？聰明的您是否找到了線索：正常的豎式除法要經曆試商、乘積、求差、比較餘數和除數4個小步驟，“短除法”省略了後面3個步驟，是一種直接寫商的除法。這豈止是“短”了，那是“相當的短”了！為何如此？因為短除法的特點在于除法的繼續施加，可以循環往下，重複第二次、第三次……上一步的商旋即變為下一步的被除數，如果将這個過程用普通除法豎式表達出來，會寫啰嗦的一大堆，如下圖：

　　簡便是短除法的優點，但也有代價。如果被除數很大，心算弱的小朋友估計得借助于普通除法豎式另行求商。相信，您會對此感同身受。

　　利用短除法求取兩個自然數的最大公因數，其實質是對這兩個自然數作質因數分解，而且首先羅列相同的質因數。教材61頁示例：（24，36）＝12的計算過程，同以下：

　　24＝（2×2×3）×2

　　36＝（2×2×3）×3

　　質因數分解是具有“标準形式”的，比如：将質因數從小到大排列，以幂次方乘積的形式表達（以後有工夫了，詳細讨論）。利用短除法求最大公因數，打亂了這種标準形式：它将兩個自然數相同的質因數排在前面，不同的質因數過濾在後。這種“相同”是建立在一一對應的基礎上的，能夠對應的最大部分的乘積即為兩個自然數的gcd。

　　掌握這種方法會讓小學時期的我們自信滿滿、神采奕奕。

　　方法三：輾轉相除法

　　這個方法其實是我國古代“更相減損術”的小升級，如圖：

人教五數下冊67頁

　　如果上面的話讓您感到費解，是因為您沒有拿起紙和筆舉例子。（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行左右就夠了。到那時，您會真正發現“算法”的神奇！

　　有好奇與探索相伴的人生是精彩的，就好比旅行途中發現别樣的風景一樣。

　　再會。

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!