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

資料來源
科學研習月刊41-1
文/謝新傳
有一天,彥廷和佩珊兩人在談旅遊的事,他們很關心出遊日期是週幾,彥廷問佩珊:「今年(公元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),並且記為a≡b(mod m)。,這裏順便一提,同餘的概念和符號都是數學王子高斯發明的。

就上面的例子而言:
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)a+c ≡ b+d(mod m)
(性質2)a − c ≡ b − d(mod m)
(性質3)a × c ≡ b × d(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)