生活科學補給站

化學

生物

健康教育

地球科學

數學

生活科技

物理

專題導言

STEAM

美妙的數字世界-同餘的世界

文/謝新傳
有一天，彥廷和佩珊兩人在談旅遊的事，他們很關心出遊日期是週幾，彥廷問佩珊：「今年(公元2002年，是平年)的一月一日是星期二，那麼明年的一月一日是星期幾？」，佩珊幾乎連想都沒想，就回答彥廷說；「公元2003年的一月一日是星期三」。彥廷對她的心算速度感到十分佩服也覺得很訝異，就請教佩珊為什麼能算這麼快？佩珊說從一月一日算起再過365 天(就是52週又1天)，365除以7得商52餘1，52 這個數在這裏並不重要，而這個「餘數」1 才是重點。而一加一等於二，所以明年的一月一日就是星期三。

在上面這一小段故事中，出現了365 和1 這兩個自然數，這兩個數字當然是不相等同的，但在〝餘數世界〞裏，它們被看成是〝相同〞的數。比如365和1用7去除，結果餘數都是1，我們就說365 和1 同餘。

在數學上，如果整數a與b同時除以m(m≠0)所得的餘數相同(也就是說(a-b)能被m整除)時，我們就說a與b(模m)同餘，或著讀作a同餘於b(模m)，並且記為ａ≡b(mod ｍ)。，這裏順便一提，同餘的概念和符號都是數學王子高斯發明的。

就上面的例子而言：
1 ≡ 8 ≡ 15 ≡ 22 ≡ 29 ≡ 36 ≡ ．．．． ≡ 358 ≡ 365(mod 7)
又比如：30 ≡ 9(mod 7)　　100 ≡ 52(mod 12)
甚至於　97 ≡ -3(mod 4)　　-37 ≡ -13(mod 6)

底下先介紹有關同餘的幾個重要性質之後，就會帶領同學進入豐富的數字世界。
§如果a≡b(mod m) 而且c≡d(mod m)
那麼
（性質1）ａ＋ｃ ≡ ｂ＋ｄ(mod m)
（性質2）ａ − ｃ ≡ ｂ − ｄ(mod m)
（性質3）ａ × ｃ ≡ ｂ × ｄ(mod m)
（性質4）an ≡ bn (mod m)
上述這四個「數字性質」證明並不困難，所以留著給同學自行證明。現在將這幾個簡單的數字性質加以活用，介紹如下：
(1)三的倍數判別法：
一個整數各位數碼的總和除以3的餘數與該整數除以3的餘數是相同的。進一步說，一個整數如果各位數碼的總和如果是3的倍數，那麼它也就是3 的倍數。

為了讓同學容易瞭解起見，現在先用兩位數來說明：
有一個二位數ab，它的十位數是a，個位數是b ，那麼它的代數表示式為10 ×a+b 。

而10≡1(mod 3) , 而由（性質3）可知10×a≡1×a(mod 3)即10a≡a(mod 3)
又已知b≡b(mod 3)
再由（性質1）我們可得到下面結論：10a+b≡a+b(mod 3)
由上式我們知道一件事，(10a+b)和(a+b)去除以3 所得的餘數相同。更進一步而言，當(a+b)是三倍數時，原數10a+b也會是三的倍數。

其次我們再來證明一般n 位數的情形：設an−1 an−2 an−3............ a1 a0為一個n位數，他的代數式表示為：
an−1 ×10n−1+ an−2 ×10n−2+ an−3 ×10n−3+.............. a1×101+ a0
而其中 a0 ≡ a0(mod 3)
10≡ 1(mod 3) 而由（性質3）可知 10×a1 ≡ a1(mod 3)
102≡ 1(mod 3) 同理可知 102×a2 ≡ a2(mod 3)
......................
......................
10n−2 ≡ 1(mod 3) 同理可知 10n−2×an−2 ≡ an−2(mod 3)
10n−1 ≡ 1(mod 3) 同理可知 10n−1×an−1 ≡ an−1(mod 3)

再由(性質1)可得到如下的式子：
10n−1×an−1+10n−2×an−2+ .......102×a2+101×a1+ a0 ≡ an−1 +an−2+.........+ a2+a1 + a0(mod 3)
易言之n 位數an−1 an−2.......a2 a1 a0 和an−1+an−2+.........+ a2+a1 + a0 同餘
也就是說n位數an−1 an−2.......a2 a1 a0它除以3 的餘數和an−1 +an−2 +.........+a2 +a1 + a0 除以3 的餘數相同。

比如說4 2 0 8 ÷ 3 餘2 ， 而(4+2+0+8)÷3 也餘2
更進一步而言，當an − 1 + an −2+.........+ a2+a1 + a0 是3 的倍數時， n 位數an−1 an−2.......a2a1 a0 也會是3 的倍數。
(2)十一的倍數判別法：
一個正整數，它的奇位數碼的總和減去偶位數碼的總和除以11 的餘數和原數除以11 的餘數相同。更進一步說，一個正整數，它的奇位數碼的總和減去偶位數碼的總和如果是11的倍數(0也是11的倍數)，那麼這個整數也就是11 的倍數。

《證明》同上題一樣，我們先從一個簡單的三位數946 說明：
因 6 ≡ 6 (mod 11)
10 ≡ −1(mod 11) → 40 ≡ −4(mod 11)
100 ≡ 1 (mod 11) → 900 ≡ 9(mod 11)
由以上三式及(性質1)知：946 ≡9+6−4≡0 (mod 11)
946 就是11 的倍數

現在我們作一般性的證明：
假設an−1 an−2 an−3............ a1 a0為n位數，他的代數式表示為：
an−1 × 10n-1 + an-2 × 10n-2 + an-3 × 10n-3 +.............. a1 + 101+ a0
其中a0 , a2 , a4 , a6 , a8 ,.............為奇數位　a1 , a3 , a5 , a7 , a9 ,.............為偶數位
而
1 ≡ 1(mod 11)
10 ≡ −1(mod 11)
102 ≡ 1(mod 11)
103 ≡ −1(mod 11)
..........................

我們發現10 的奇數乘方，它和-1 同餘而10 的偶數乘方，它和1 同餘如此一來，我們可得到下面同餘關係式：
當n 是奇數時
an−1 ×10n−1+ an−2 ×10n−2+ an−3 ×10n−3+..............a1 ×101+ a0 ≡ (an−1+ an−3+ an−5+...... a2+ a0)−( an−2+ an−4+an−6+...... a3+ a1) (mod 11)
若n 是偶數時
an−1 ×10n−1+ an−2 ×10n−2+ an−3 ×10n−3+..............a1 ×101+ a0 ≡ (an−2+ an−4+ an−6+...... a2+ a0)−( an−1+ an−3+an−5+...... a3+ a1) (mod 11)
此即原數同餘於奇位數碼的總和減去偶位數碼的總和
比如4719這個數的奇數位總和減去偶數位總和=(9+7)-(4+1)=11是11 的倍數，果然4719=11×429
再看23456 這個數的奇數位總和減去偶數位總和=(2+4+6)-(3+5)=4果然， 23456÷11=2132——餘4
(3)求21000 除以13 的餘數
我們首先知道2的6次方26=64 ,它比13的5倍少1

因此
26 ≡ −1 ( mod 13 )
那麼由(性質4)可得 (26)2 ≡ (−1)2 ( mod 13)
即212 ≡ 1( mod 13 )⇒ (212)83≡ 1 83 ( mod 13 ) ⇒ 2996 ≡ 1 (mod 13 )

其次我們又知道1000÷12=83........餘4
所以2996 x24≡ 1 x24 ( mod 13 ) 亦即 21000 ≡ 16 ( mod 13 )
而眾所皆知16除以13的餘數是3，故21000 除以13 的餘數就是3
(4)求101000除以7的餘數
首先我們很容易發現1001 是7 的倍數，也就是
1000≡−1 (mod 7)
底下我們再使用一些同餘的簡單性質，即可將本題答案求出：
既然1000≡−1 (mod 7)⇒ 1000333 ≡ (−1)333 (mod 7)
亦即10999 ≡ −1 (mod 7)
⇒10999x10 ≡ −1x10 (mod 7)
⇒101000 ≡ −10 (mod 7)
⇒101000 ≡ −10 +14(mod 7)
⇒101000 ≡ 4(mod 7)