倍數判別法

引子

在《素數判別法》一文中,本網為大家介紹了一個早已為大家知曉的素性 (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 為奇數時,若 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 的倍數。

 

去掉尾巴的方法

看看 19 的倍數的判別方法吧。

判別 46892 是否 19 的倍數。

先把 46892 的「尾巴」2 砍掉,再把「尾巴」的兩倍加在餘數上,即 4689 + 2 * 2 = 4693。

再把 4693 的「尾巴」3 砍掉,再把「尾巴」的兩倍加在餘數上,即  469 + 2 * 3 = 475。

再把 475 的「尾巴」5 砍掉,再把「尾巴」的兩倍加在餘數上,即  47 + 2 * 5 = 57。

再把 57 的「尾巴」7 砍掉,再把「尾巴」的兩倍加在餘數上,即  5 + 2 * 7 = 19。

餘下 19,故 46892 亦是 19 的倍數。 (46892 = 19 * 2468)

 

原理也很簡單,設某數為 M =  10A + B,其中 B 為個位數。去掉「尾巴」,再把「尾巴」的兩倍加在餘數上,即新數為 N = A + 2B。

我們知道 2M - N = 2(10A + B) - (A + 2B) = 20A + 2B - A - 2B = 19A,為 19 的倍數。即一是 M, N 同為 19 的倍數,或是 M, N 同不是 19 的倍數。

我們重覆步驟至最後一個位,便知數 M 和 N 是前者或是後者了。

 

其實這方法亦適用於判別一眾個位為「九」的整數的倍數,如 29、39、49、...

我們假設先得去掉「尾巴」,再把「尾巴」的 a 倍加在餘數上,設某數為 M =  10A + B,其中 B 為個位數,而新數為 A + aB。

另 aM - N = 29n,a(10A + B) - (A + aB) = 29n,10aA + aB - A - aB = 29n,(10a - 1)A = 29,即取 a = 3。

故我們以掉「尾巴」,再把「尾巴」的 3 倍加在餘數上的方法便可測試某數是否 29 的倍數了。

 

同理,我們亦可以此法判別一眾個位為「一」的整數的倍數,如 11、21、31、...

方法只是把「尾巴」加在餘數上改為從餘數中減掉便成,至於減掉多少倍的「尾巴」,則要看對象是 21 的倍數還是 51 的倍數了。

 

總結

對於某一因子 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),而用第二個方法計算。

 

第四 ,我們亦可運用去掉「尾巴」的方法來判別某數是否為那些個位為 1 或 9 的數,如 19、29、31等數的倍數。但此法的缺點是我們得一步一步來幹,對於數位較大的數,判別往往更加費時。

 

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

 

參考文獻及網址:

曹昌東 ; 張向晴 , "特殊質因數判別法" 自 數學快遞第七期, 台北 : 三民書局