數的整除特徵及其應用（數的整除性進一步討論）

2023-07-22 13:30:38 1

此圖顯示我們試圖找到更多的數能有簡便的判斷方法

比較遺憾，只發現了37,41,73,137,271等

說到現在，50以內的質數我們已經找到規律的有2,3,5,7,11,13, 37,41,還有剩下的17,19,23,29,31,43,47怎麼辦呢？別急，博主還有辦法！那就是截尾法。

截尾法，顧名思義，就是截斷尾巴，已知一個N位的整數M，要判斷是不是被一個質數p整除，除去我們已經發現的，就只能用這種辦法了。M截斷1位後，剩下的數顯然比M小，循環操作下去，直到能分辨出結果是不是能被p整除。不過，我們不能光截斷，否則與M不同餘，我們的操作就是錯誤的，還需要增加或減少被截斷數的倍數，以保證操作完的數Q與M對質數p是同餘的。

給定的數M，我們把它分成兩部分，尾數設為b，剩下的設為a，那麼M=10a b。因為b只有一位數，a有可能有很多位數，所以，我們需要根據同餘的性質，儘量簡化a的係數，顯然，係數為1最方便，這就是截尾法的核心所在。

下面以17為例，如果10a b能夠被17整除，那麼5(10a b)也可以被17整除，而5(10a b) = 50a 5b = 51a-a 5b = 51a-(a-5b)，51=3*17可以整除17，因此，M=10a b與a-5b對17同餘，M是否整除17相當於a-5b是否整除17。也就是截斷尾數後，還要減去尾數的5倍，如果結果能被17整除，那麼原數就能被17整除。如此繼續進行，直到結果能夠容易判斷為止。

舉個例子，587639能否被17整除？

下面我們按照步驟計算：

587639->58763-9*5=58718

58718->5871-8*5=5831

5831->583-1*5=578

578->57-8*5=17，可以被17整除，故原數可以被17整除。

好了，搞定了17，我們看看19。