假如人有十二隻手指... (下)

4. 整除性

「整除性」(Divisibility)問題就是有關某一整數能被甚麼整數整除的問題，我們說整數n能被非零整數m整除(這裡n和m可以是負數)當且僅當存在一個整數k使得n = mk，在「數論」(Number Theory)中，一般把「m可被n整除」記作

n | m

我們在小學時曾學過一些「整除性判定規則」，以下列出首13個正整數的判定規則(請注意由於7和13的規則較難應用，所以以下提供兩種規則)：

規則1：	對任何整數n，都有1 | n。
規則2：	若某整數n的最末一位數字可被2整除(即等於0、2、4、6或8)，則2 | n。
規則3：	若某整數n的各位數字之和可被3整除，則3 | n。
規則4：	若某整數n的最末兩位數字可被4整除，則4 | n。
規則5：	若某整數n的最末一位數字可被5整除(即等於0或5)，則5 | n。
規則6：	若某整數n可同時被2和3整除，則6 | n。
規則7a：	把某整數n從右到左每3個位分成一節，並計算第1節 − 第2節 + 第3節 − 第4節 + ...，若所得結果可被7整除，則7 | n。
規則7b：	把某整數n的個位數截去，再從餘下的數中，減去被截個位數的2倍，若所得結果可被7整除，則7 | n。
規則8：	若某整數n的最末三位數字可被8整除，則8 | n。
規則9：	若某整數n的各位數字之和可被9整除，則9 | n。
規則10：	若某整數n的最末一位數字可被10整除(即等於0)，則10 | n。
規則11：	若某整數n的奇位數字之和與偶位數字之和的差可被11整除，則11 | n。
規則12：	若某整數n可同時被3和4整除，則12 | n。
規則13a：	把某整數n從右到左每3個位分成一節，並計算第1節 − 第2節 + 第3節 − 第4節 + ...，若所得結果可被13整除，則13 | n。
規則13b：	把某整數n的個位數截去，再在餘下的數中，加上被截個位數的4倍，若所得結果可被13整除，則13 | n。

以下是上述規則的一些應用例子。首先看「規則12」的例子，這是「規則3」和「規則4」的結合。由於1728的末二位數字28可被4整除，並且其各位數字之和1 + 7 + 2 + 8 = 18可被3整除，因此1728可同時被3和4整除，由此知12 | 1728。其次看「規則11」的例子，由於14641的奇位數字之和是1 + 6 + 1 = 8，偶位數字之和是4 + 4 = 8，這兩者之差8 − 8 = 0可被11整除，因此11 | 14641。接著看7的規則，我們交替使用以上提供的兩種規則求6049382661能否被7整除。根據「規則7a」，我們先把這個數分為4節：第1節 = 661，第2節 = 382，第3節 = 49，第4節 = 6，然後求661 − 382 + 49 − 6 = 322。接著應用「規則7b」，先把322的個位數2截去，得32，然後從32減去2的2倍，得28。由於28能被7整除，所以7 | 322，也就是7 | 6049382661。


可是，以上的規則(除了「規則1」外)究竟有何理據？首先考慮「規則8」，給定任何整數n並且其最末三位數字為m，那麼我們可以把n寫成1000k + m (k可以為0)。若8 | m，則我們可以把m寫成8j。由此有

n = 1000k + m = 8(125k + j)

由於125k + j是整數，所以8 | n。由此證得「規則8」成立，請注意上述證明的關鍵是利用了8是1000的因數這個事實。利用類似原理，我們也可證明「規則2、4、5和10」也成立。



接著考慮「規則6」，這條規則要用到數論中的以下定理(證明從略)：



定理1：設p為整數，若兩整數m與n互質，並且m | p並且n | p，則mn | p。



由於2與3互質，根據「定理1」，可知若某整數p可同時被2和3整除，則p可被6整除，「規則12」也是基於類似的理據。



接著考慮「規則7b」，給定任何整數n，我們可以把n寫成10a + b (0 ≤ b ≤ 9)，其中b就是n的個位數。把n的個位數截去，再從餘下的數中，減去被截個位數的2倍，我們便可得到a − 2b。若這個數可被7整除，則我們有a − 2b = 7k，亦即a = 7k + 2b。由此有

n = 10a + b = 70k + 20b + b = 7(10k + 3b)

由於10k + 3b是整數，所以7 | n。由此證得「規則7b」成立，請注意上述證明的關鍵是利用2 × 10 + 1可被7整除這個事實。類似地，利用(−4) × 10 + 1可被13整除這個事實，我們可以證明「規則13b」也成立。



對於其餘的規則，我們要用到「數論」中的「同餘」(Congruence)概念。設n為正整數，我們說兩個整數p與q是「模n同餘」的(Congruent Modulo n)，記作

p ≡ q (mod n)

當且僅當以n除p和以n除q所得餘數相等。舉例說，我們有6 ≡ 9 (mod 3)，因為這兩個數都可被3整除(即以3除這兩個數所得餘數均為0)。請注意我們亦可以把「同餘」定義為(證明從略)：

p ≡ q (mod n)當且僅當n | (p − q)     (3)

舉例說，由於2 − (−1) = 3可被3整除，因此根據(3)，我們有2 ≡ −1 (mod 3)。根據「同餘」的定義，我們可以推出以下定理(證明從略)：



定理2：設有多項式P(x) = c_mx^m + c_m−1x^m−1 + ... + c₁x + c₀，若a ≡ b (mod n)，則P( a ) ≡ P( b ) (mod n)。



我們可以利用「定理2」來證明「規則11」。設n為任意整數，那麼在十進制下，n可以表達為n = P(10) = c_m10^m + c_m−110^m−1 + ... + c₁10 + c₀，其中c₀、c₁...都是介乎0與9之間的整數，分別為n的個位數、十位數...。由於10 − (−1) = 11可被11整除，根據(3)，我們有10 ≡ −1 (mod 11)。因此根據「定理2」，我們有P(10) ≡ P(−1) (mod 11)，即n = P(10)可被11整除當且僅當P(−1)可被11整除。但

P(−1) = c₀ − c₁ + c₂ − c₃ + ... + (−1)^m c_m

上式正是n的奇位數字之和與偶位數字之和的差，「規則11」至此得證。請注意上述證明的關鍵是利用10 ≡ −1 (mod 11)，類似地，我們亦可利用10 ≡ 1 (mod 3)和10 ≡ 1 (mod 9)來證明「規則3」和「規則9」。



把以上證明略加修改，便可證明「規則7a」。設n為任意整數，那麼n可以表達為n = P(1000) = c_m1000^m + c_m−11000^m−1 + ... + c₁1000 + c₀，其中c₀、c₁...為介乎0與999之間的整數，分別為把n從右到左每3個位分成一節後所得的第1節數字、第2節數字...。由於1000 − (−1) = 1001可被7整除，根據(3)，我們有1000 ≡ −1 (mod 7)。因此根據「定理2」，我們有P(1000) equiv;
P(−1) (mod 7)，即n = P(1000)可被7整除當且僅當P(−1)可被7整除。但

P(−1) = 第1節 − 第2節 + 第3節 − 第4節 + ... + (−1)^m第m節

「規則7a」至此得證。類似地，我們亦可利用1000 ≡ −1 (mod 13)來證明「規則13a」。



我們可以把上述原理推廣至十二進制，從而得到十二進制下首13個正整數的「整除性判定規則」如下：

規則112：	對任何整數n12，都有112 | n12。
規則212：	若某整數n12的最末一位數字可被212整除(即等於012、212、412、612、812或A12)，則212 | n12。
規則312：	若某整數n12的最末一位數字可被312整除(即等於012、312、612或912)，則312 | n12。
規則412：	若某整數n12的最末一位數字可被412整除(即等於012、412或812)，則412 | n12。
規則512a：	把某整數n12從右到左每2個位分成一節，並計算第1節 − 第2節 + 第3節 − 第4節 + ...，若所得結果可被512整除，則512 | n12。
規則512b：	把某整數n12的最右一位數截去，再從餘下的數中，減去被截最右一位數的212倍，若所得結果可被512整除，則512 | n12。
規則612：	若某整數n12的最末一位數字可被612整除(即等於012或612)，則612 | n12。
規則712a：	把某整數n12從右到左每3個位分成一節，並計算第1節 − 第2節 + 第3節 − 第4節 + ...，若所得結果可被712整除，則712 | n12。
規則712b：	把某整數n12的最右一位數截去，再在餘下的數中，加上被截最右一位數的312倍，若所得結果可被712整除，則712 | n12。
規則812：	若某整數n12的最末兩位數字可被812整除，則812 | n12。
規則912：	若某整數n12的最末兩位數字可被912整除，則912 | n12。
規則A12：	若某整數n12可同時被212和512整除，則A12 | n12。
規則B12：	若某整數n12的各位數字之和可被B12整除，則B12 | n12。
規則1012：	若某整數n12的最末一位數字可被1012整除(即等於012)，則1012 | n12。
規則1112：	若某整數n12的奇位數字之和與偶位數字之和的差可被1112整除，則1112 | n12。

可以看到，由於2、3、4、6和12都是12的因數，上表中的「規則2₁₂、3₁₂、4₁₂、6₁₂和10₁₂」都很簡單，只須看n₁₂的最末一位數字。此外，由於8和9都是144的因數而144 = 100₁₂，「規則8₁₂和9₁₂」也很簡單，不過它們要看n₁₂的最末兩位數字。「規則B₁₂和11₁₂」則可分別應用12 ≡ 1 (mod 11)和12 ≡ −1 (mod 13)以及「定理2」來證明。至於「規則A₁₂」，則可以用2與5互質這個事實以及「定理1」來證明。


「規則7₁₂a」跟十進制下的「規則7a」相同，這是因為我們有1728 ≡ −1 (mod 7)，而1728 = 1000₁₂。此外，由於144 ≡ −1 (mod 5)，「規則5₁₂a」跟「規則7₁₂a」很相似，所不同者是前者把n₁₂從右到左每2個位(而非每3個位)分成一節。



「規則7₁₂b」的原理跟十進制下的「規則7b」相同，即給定任何整數n₁₂，我們可以把n₁₂寫成10₁₂a₁₂ + b₁₂ (0₁₂ ≤ b₁₂ ≤ B₁₂)，其中b₁₂就是n₁₂的最右一位數。把b₁₂截去，再在餘下的數中，加上b₁₂的3₁₂倍，便可得到a₁₂ + 3₁₂b₁₂。若這個數可被7₁₂整除，則我們有a₁₂ + 3₁₂b₁₂ = 7₁₂k₁₂，亦即a₁₂ = 7₁₂k₁₂ − 3₁₂b₁₂。由此有(註5)

n₁₂ = 10₁₂a₁₂ + b₁₂ = 70₁₂k₁₂ − 30₁₂b₁₂ + b₁₂ = 7₁₂(10₁₂k₁₂ − 5₁₂b₁₂)

由此證得7₁₂ | n₁₂，即「規則7₁₂b」成立。利用相同原理，也可證明「規則5₁₂b」成立。



總括而言，在十進制下，有兩條規則(「規則6和12」)乃由其他規則定義，兩條規則(「規則7a和13a」)涉及三位數加減運算。而在十二進制下，有一條規則(「規則A₁₂」)乃由其他規則定義，一條規則(「規則5₁₂a」)涉及兩位數加減運算，一條規則(「規則7₁₂a」)涉及三位數加減運算。至於其餘的規則，兩者的難度不相上下。因此從整體而言，在十二進制下判定首13個正整數的整除性似乎較十進制略為容易。

全 文 完

---

註5：請注意下式須用到7₁₂ × 10₁₂ = 70₁₂、−30₁₂ + 1₁₂ = −2B₁₂以及「B因歌」中的「57得2B」等運算結果。