同餘小問題

同餘 (Congruence) 是研習整數性質中一不可少的工具。如判斷整除性 (Divisibility) :

若 a = 0 (mod m),我們便可說 a 是 m 的倍數或 m 整除 a。

現在讓我們看看一些同餘小問題,當中有不少是取材自數學競賽 (Mathematics Competition) 或 數學奧林匹克 (Mathematical Olympiad) 的。

求 20052005 除以 7 的餘數。

答:即考慮 20052005 在模 (Modulo) 7 的剩餘。因為 2005 = 3 (mod 7),所以 20052005 = 32005 (mod 7),但留意,這不等於 33 。所以我們現在得計算 32005 (mod 7) 是多少。 32 = 9 = 2 (mod 7), 33 = 2*3 = 6 = -1 (mod 7)。因此 32005 = 33*668+1 = (33)668*3 = (-1)668 *3 = 1*3 = 3 (mod7)。所以 20052005 除以 7 的餘數是 3 。

方法是求取 3n = ± 1 (mod 7) 中的 n 值,再以 ± 1 把指數減少,再行計算,以求答案。

 

求 460 除以 23 的餘數。

答:即考慮 460 在模 23 的剩餘。但我試以另一方法計算此題。 43 = 64 = -5 (mod 23),故 46 = (-5)2 = 25 = 2 (mod 23) , 而 412 = 22 = 4 (mod 23)。那麼 460 = 412*5 = 45 = 43*42 = -5*16 = -80 = -11 (mod 23) ,所以 460 除以 23 的餘數是 12。

方法是尋找指數 (60) 的因子 (如:12),計算 412 的值,再代入原式,把該指數減少,再行計算,以求答案。

 

證明 237 - 1 是 223 的倍數。

答:即考慮 237 - 1 = 0 (mod 223)。但由於 223 比較大,故尋找 ± 1 是行不通的,但指數 37 又是素數,故我們只得把 37 分柝成 32 + 5,再行計算。因 27 = 128,28 = 256 = 223+33,所以 28 = 33 (mod 223)。其實這 28 是2 的第一個次方數大於 223,那麼我們才可把數值在模 223 下縮少,便利計算。 216 = 33*33 = -26 (mod 223),232 = (-26)*(-26) = 7 (mod 223),而 25 = 32。所以 237 = 232 * 25 = 7*32 = 1 (mod 223)。證畢。

 

求 31997 的最後兩位數。

答:即考慮 31997 除以 100 的餘數,或 31997 在模 100 下的剩餘,但 100 這個模數寫太大,若以 3 的次方數一一去數的話,計算量恐怕也不少。故我們考慮 31997 = a (mod 100) 時留意到 100 = 4 * 25 且 (4,25) = 1 於是由 求 n 使 3n = 1 (mod 100) 轉為求 n 使 3n = 1 (mod 4) 及 3n = 1 (mod 25) 。 不難求出 32 = 1 (mod 4),但模 25 的可要花點時間,最後得 310 = -1 (mod 25) ,即 320 = 1 (mod 25)。因為 20 = 2*10 所以 20 便是我們目標的 n 了。 320 = 1 (mod 100),所以 31997 = 320*99 + 17 = 1 * 317 = 317 (mod 100)。但 36 = 729 = 29 (mod 100), 317 = 36*2+5 = 292 * 243 (mod 100) ,29*29 = 841,所以 31997 = 317 = 41*43 = 63 (mod 100)。所以,31997 的最後兩位數是 63。

 

證明當 p 不少於 5 的素數時,p2 + 2 為一合數。

答:觀察 52 + 2 = 27, 72 + 2 = 51 等都是 3 的倍數,我們相信 p2 + 2 會全是 3 的倍數,故考慮 p2 + 2 (mod 3)。由於 p 為不少於 5 的素數,所以 p = ± 1 (mod 3) ,而 p2 + 2 = 0 (mod 3),所以 p2 + 2 甯陘@合數。證畢。

 

以 pi 表示第 i 個素數,證明 p1 * p2 * p3 * ...... * pn + 1 不會是一平方數。

答:其中 p1 = 2,而 pi 為奇數,當 i 不少於 2 時。故 N = p1 * p2 * p3 * ...... * pn 為一偶數,但不會是 4 的倍數,即 N = 2 (mod 4),所以 N + 1 = 3 (mod 4),這不會是一平方數,因在模 4 下,平方數只會等於 0 或 1。證畢。

 

證明任何三個連續整數 (Consecutive Integers) 的立方和均為 9 的倍數。

答:設 N = (n-1)3 + n3 + (n+1)3 = 3n(n2 + 2),若 n = 0 (mod 3),則 N 已含有 3 這個因子兩次,即 N 是 9 的倍數。若 n = ± 1 (mod 3) ,則 n2 + 2 = 0 (mod 3),而這亦同樣使 N 含有3 這個因子兩次 ,即 N 是 9 的倍數。證畢。

 

證明 70! = 61! (mod 71)。

答 : 70! = 61! * 62 * 63 * 64 * ..... * 70,若 70! = 61! (mod 71) ,則必須證明 N = 62 * 63 * 64 * ...... * 70 = 1 (mod 71)。但 70 = -1 (mod 71)、69 = -2 (mod 71)、68 = -3 (mod 71)、......、62 = -9 (mod 71):所以 N = (-1) * (-2) * (-3) * ...... * (-9) = - 9! (mod 71),1*2*3*4*5 = 120 = -22 (mod 71),-22*6 = -132 = 10 (mod 71) ,10*7 = 70 = -1 (mod 71),-1*8*9 = -72 = -1 (mod 71),所以 -9! = 1 (mod 71),即 N = 62 * 63 * 64 * ...... * 70 = 1 (mod 71)。所以證畢。

 

證明對任何正整數 n,下面五個同餘式 (Congruence Expression) 中至少有一個成立:

n = 0 (mod 2),n = 0 (mod 3),n = 1 (mod 4),n = 5 (mod 6),n = 7 (mod 12)

答:我們留以到五個模數的最小公倍數 (Least Common Multiple, L.C.M.) 為 12。故我們考慮所有模 12 的可能性:式 1 包括了所有的 n = 0, 2, 4, 6, 8, 10 (mod 12),而式 2 包括了所有的 n = 0, 3, 6, 9 (mod 12) ,而式 3 包括了所有的 n = 1, 5, 9 (mod 12) ,而式 4 包括了所有的 n = 5, 11 (mod 12),最後的式 5 包括了 n = 7 (mod 12)。即 0 至 11所有可能性均為其中一式或以上所包括,故證畢。