作者 | 劉瑞祥

來源 | 說短論長

編輯 | 遇見數學

本文原創性很低，但是我希望大家讀了以後能“真的”讀懂，切實理解其中道理，而不是囫囵吞棗。本文涉及初等數論的三個非常重要的定理（算法），均出自《幾何原本》。

如果兩個數都能被第三個數整除，則這兩個數的和、差一定能被第三個數整除；如果兩個數有且隻有一個能被第三數整除，則這兩個數的和、差一定不能被第三個數整除。

設有兩個數 、，欲求其最大公約數，可以用大數除以小數，取其餘數（肯定小于一開始的較小數，我們不妨稱這一步得到的餘數是第一餘數），再以開始所給的較小數除以第一餘數，再取餘數（即第二餘數），以後以第一餘數除以第二餘數達到第三餘數，第二餘數除以第三餘數得到第四餘數…直至餘數為 時，上一次的餘數即為初始兩個數的最大公約數。

例：設初始的兩個數為 和 ，以 除以 得到第一餘數為 ，再以 除以 得到第二餘數為 ，以 除以 得到第三餘數為 3，因為 12 能被 3 整除，所以 3 是最大公約數。

→ 和 的最大公約數是 。

道理很簡單： 取餘數，其實可以看做從 裡連續減去 直到減不開為止。而公約數 （姑且不管是不是最大）是 和 共同的約數，即 、 都是 的倍數，所以從 中連續減去 ，兩個同為 倍數的數做減法，得到的餘數（這裡是第一餘數）當然還是 的倍數，此即前面提到的預備知識。以後輾轉進行下去，每一次得到的餘數當然也還是 的倍數。直到得到這個 ，也就是整除了。

那為什麼是最大公約數呢？因為如果不是最大的，換句話說就是還有更大的，比如是 。那麼這個 就在前面的過程中被“跳過去”了。那麼顯然就違背了預備知識。因為本來任何一步裡兩個數的全部約數都滿足預備知識，結果這麼一來肯定有的不滿足了。

以上就是著名的歐幾裡得算法，隻不過當年歐幾裡得用詞遠比這嚴謹。這個算法有什麼用呢？它比起小學學的短除法，最大的好處是不用一個個的嘗試某個數是不是公約數。短除法對于大數很麻煩，比如求 和 的最大公約數需要一個個嘗試，如果給的兩個數更大，特别是兩個數的公共質因數很大，就更麻煩（最近一位老師讓學生計算 和 的最大公約數，許多學生就算不出來）。另外用輾轉相除法還可以立刻得出一個結論：相差為 的兩個正整數互質。

這個關系很簡單：兩個數的最大公約數和最小公倍數，二者的乘積等于原來兩個數的乘積。

首先我們看兩個互質數的情況：互質數的最大公約數就是 ，最小公倍數就是這兩個數的乘積，顯然符合這個關系，但是任意兩個正整數呢？

要理解這個關系也不難，假設兩個數 、 的最大公約數是 ，即 ，，則顯然 ，而括号裡的 恰好就是最小公倍數。如果還有人覺得不放心，可以回憶一下短除法的計算過程：對于兩個數的情況，“側面的”乘在一起就是最大公約數 ，側面的和“底下的”乘在一起（無論計算最大公約數還是最小公倍數，側面的隻取一次）就是最小公倍數 。

這個定理有很多證明方法，但最簡單的是這個：假設質數是有限的，将全部各個質數乘起來再加 ，則這個新得到的數肯定和全部質數的乘積互質，即不能被已有的各個質數整除，所以是一個新的質數。這就和前面矛盾了。

大家要注意，這裡并不是說若幹質數乘起來再加 一定會得到新的質數，實際上也可能得到一個能被其它質數整除的合數。比如 、 都是質數，而 卻不是，它是 的倍數，注意 不是

用連續相乘的方法還可以求任意長度的連續合數數列。比如我要生成連續 個合數，就可以先計算出 ，然後用這個結果加 、加 、加 一直到加 ，因為 含有 的每個因子，所以加 就是 的倍數，加 就是 的倍數，如此等等。可以想見，用這樣的方法得到連續的千百萬個合數也是沒有問題的。但是這樣得到的數列肯定不會是最小的，即以此題為例，實際上在這之前我們就有 連續七個合數，而更前面還有 、、、、、、 等多個連續的五合數數列。另外不但從 乘到 加 直至加 是合數，而且 前面還有 也都是合數，也就是說 連續十三個數都是合數。

一方面質數是無窮無盡的，另一方面連續的合數數列可以要多長有多長，多麼神奇的數學。

另外我要說一點：初等數論在小學數學中是非常特别的内容，它的計算和小學數學其它部分明顯不同，主要是對邏輯的要求比較高，如果隻讓學生機械地記憶和應用這些内容，那就太可惜了。雖然誰出的卷子都不要求學生寫算理，但是算理最重要。至于有的老師總覺得學生不一定能理解其中的道理，那我隻能說：如果你不去發展學生的思考能力，那學生就永遠也無法發展思考能力，思考能力的發展是長期而艱巨的，但不可缺少。為什麼五年級學生理解不了被 整除數的特性？因為他四年級的時候沒有發展相應能力，四年級時為什麼沒有發展起來？因為他三年級時…老師總是告訴學生最後的結論，如同廚子總是把菜做好了再端上來，顧客是不會學會做菜的。

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