倍數判別法

引子

在《素數判別法》一文中，本網為大家介紹了一個早已為大家知曉的素性 (Primality) 判別方法，即試除法 (Trial Division)。但當我們作試除時，若能及早斷定 n 為某數的倍數 (Multiple) ，會大大減少我們的計算時間，特別是在心算時。故本章會為大家介紹一些含常用的因子的數的判別之法，目的只是讓我們「相數」時也會快一點。

 

二五次方數

試一整數 N 以十進制表示為 an10n + an-110n-1 + ...... + a0。

因為 10 = 2*5，所以 2k 或 5k 必可整除 10k。所以判斷 N 是否 2k 或 5k 只要看看 N 的最末 k 位數，是否 2k 或 5k 的倍數便可。特別地，若一數的個位為 0, 2, 4, 6, 8 (即偶數)，那數便是 2 的倍數；若一數的個位為 0 或 5，這數便是 5 的倍數。

如 ：18 是 2 的倍數，因為個位是 8。 35 是 5 的倍數，因為個位是 5 。2124 是 8 的倍數，因為最末 3 位數 124 = 8*16。

其實不單是純 2 或 5 的次方數，如 10、20 等只包含 2 或 5 素因子的數也可用上述判別法。不過我們取的 k 則是 2 或 5 的指數中最大的一個而已。

 

三和九怎麼辦

因為 10 = 1 (mod 3) 或 (mod 9) ，所以 10k = 1 (mod 3) 或 (mod 9) ，那麼 N = an10n + an-110n-1 + ...... + a0 = an + an-1 + ...... + a0 (mod 3) 或 (mod 9) 。即若 N 為 3 (或 9) 的倍數，只要其數位總和 (Sum of Digits) 又是 3 (或 9) 的倍數便行。

如： 123456789 是 3 的倍數，因為數位總和 1+2+3+4+5+6+7+8+9 = 45 是 3 的倍數。該數亦是 9 的倍數，因為數位總和同樣是 9 的倍數。但 203450122 則不是 3 或 9 的倍數了，因為數位總和 2+0+3+4+5+0+1+2+2 = 19，19不是 3 或 9 的倍數。

 

十一有辦法

因為 10 = -1 (mod 11) 所以 10k = -1 (mod 11) 當 k 為奇數 (Odd Number) 時，若 k 為偶數則有 10k = 1 (mod 11) 。所以 N = an10n + an-110n-1 + ...... + a0 = an(-1)n + an-1(-1)n-1 + ...... + a0，即把偶數位和奇數位的數分別加起來，再察看它們的差是否 11 的倍數。

當然我們亦會發現 100 = 1 (mod 11) 所以我們亦可用類此 3 或 9 的判別法，把數兩兩一組，加起來，看看是不是 11 的倍數。

如： 39237 是 11 的倍數，因為 (3+2+7) - (9+3) = 12 - 12 = 0 這正是 11 的倍數，或計算 03+92+37 = 132 = 11*12，即得同樣結果；而 40234 則不是 11 的倍數，因為 (4+2+4) - (0+3) = 10 - 3 = 7。

 

神聖與不祥同行

神以七日完成整個天地創造的過程，其中一日是休息的。故基督徒認為七這數字是神聖或完美的。但相反西方傳統卻認為 13 是代表不祥，詳可見《論盡不祥13》。但誰不知這兩數的倍數判別法竟是相同的。

因為 1001 = 7 * 11 * 13，但三數位在 11 而言不是最少的，而對 7 或 13 而言卻是。是故 1000 = -1 (mod 7) 或 (mod 13) 。所以 10k = -1 (mod 7) 或 (mod 13)，當 k 為 6 的倍數加 3 時；而若 k 為 6 的倍數則有 10k = 1 (mod 7) 或 (mod 13)。所以我們設 n 為 3 的倍數，若不是則可使 an 等數為零作補位。 N = an10n + an-110n-1 + ...... + a0 = (an102 + an-110 + an-2) * 1000 n/3 + ...... + (a2102 + a110 + a0) = (an102 + an-110 + an-2) * (-1) n/3 + ...... + (a2102 + a110 + a0) (mod 7) 或 (mod 13)，即 N (擴大至 n 為把 3 的倍數以後)，每 3 個數一組，偶數組和奇數組的數分別加起來，再察看它們的差是否 7 (或 13) 的倍數。

如： 149258361 是 7 的倍數但不是 13 的倍數，因為 (149 + 361) - (258) = 252，而這 252 是 7 的倍數但不是 13 的倍數。又如 20304050 則不是 7 的倍數但這會是 13 的倍數，因為 (020 + 050) - (304) = -234，這 -234 不是 7 的倍數卻是 13 的倍數。

 

總結

對於某一因子 K 的倍數的判別法：

第一，K 為一只含有 2 或 5 的因子的數，則察看最末 k 數位是否 K 的倍數，其中 k 為 2 或 5 的最高指數。

第二，即找尋使 10k = 1 (mod K) 的最小值 k，如 3 的 k = 1 ，9 的 k = 1。然後把 N 以 k 位數為一組分開再加起來，察看結果是否為 K 的倍數。故且分解 10k -1 對此類判別法有助，因如 999 = 33 * 37，我們便知道原來 37 的判別法是以此法但看三位數一組。但我們知道這 10k -1 恒為 9 的倍數，故把之除 9 ，便得一系列的純元數 (Repunit)。即分解純元數是我這問題有關，關於純元數的問題，詳可參看《談談純元數》或下表。

k
(10k-1)/9
素因子分解式
k
(10k-1)/9
素因子分解式
1
1
1
2
11
11
3
111
3*37
4
1111
11*101
5
11111
41*271
6
111111
3*7*11*13*37
7
1111111
239*4649
8
11111111
11*73*101*137
9
111111111
32*37*333667
10
1111111111
11*41*271*9091
11
11111111111
21649*513239
12
111111111111
3*7*11*13*37*101*9901
13
1111111111111
53*79*265371653
14
11111111111111
11*239*4649*909091
15
111111111111111
3*31*37*41*271*2906161
16
1111111111111111
11*17*73*101*137*5882353
17
11111111111111111
2071723*5363222357
18
111111111111111111
32*7*11*13*19*37*52579*333667
19
1111111111111111111
1111111111111111111
20
11111111111111111111
11*41*101*271*3541*9091*27961

註：紅色數者，為表中初現之素數。平心而言，沒有什麼人會以心算把每 19 個數歸一組相加後，再看看這是不是 1111111111111111111 的倍數。誰會幹這種事？討教計算機好了。故以後數位的純元數用途不大，不列寫了。

 

第三，即找尋使 10k = -1 (mod K) 的最小值 k，如 11 的 k = 1 ，7 的 k = 3。然後把 N 以 k 位數為一組分開再把奇數組和偶數組分別加起來，再把兩組相減，察看結果是否為 K 的倍數。在此類判別法中，分解 10k +1 會有助於了解某一數是否以 k 數位為一組，若 1001 = 7*11*13，即 7、11、13也可用此法且以三位數為一組，但對 11 而言 k = 1 比 k = 3 更少，故以三位數為一組僅如 7 和 13 兩數。對於 10k +1的分解，可看下表。

k
10k +1
分解式
k
10k +1
分解式
1
11
11
2
101
101
3
1001
7*11*13
4
10001
73*137
5
100001
11*9091
6
1000001
101*9091
7
10000001
11*909091
8
100000001
17*5882353
9
1000000001
7*11*13*19*52579
10
10000000001
101*3541*27961
11
100000000001
112*23*4093*8779
12
1000000000001
73*137*99990001
13
10000000000001
11*859*1058313049
14
100000000000001
29*101*281*121499449
15
1000000000000001
7*11*13*211*241*2161*9091
16
10000000000000001
353*449*641*1409*69857
17
100000000000000001
11*103*4013*21993833369
18
1000000000000000001
101*9901*999999000001
19
 10000000000000000001
11*909090909090909091
20
 100000000000000000001 73*137*1676321*5964848081

註：紅色數者，為表中初現之素數。老實而言，沒有什麼人會以心算把每 19 個數歸一組分奇偶組相加後，再求其差，最後還得看看這是不是 909090909090909091 的倍數。誰會幹這種事？又是這一句，討教計算機好了。故以後數位的 10k +1 用途不大，不列寫了。

當然在上述第三的情況，我們亦可考慮 102k = 1 (mod K)，而用第二個方法計算。

 

第四，若 6 或 21 這些合數，我們可以看看某數是否已符合其所有素因子的倍數要求，若是，便是該合數的倍數了。如 24 是 2 的倍數，也是 3 的倍數，所以 24 是 6 的倍數。但若檢查一數是不是 12 的倍數，我們便要檢查該數是不是同時是 4 和 3 的倍數，而不是單看 2 和 3。

 

Hosted by www.Geocities.ws

1