分解奧數題

數學奧林匹克 (Mathematical Olympiad) 也稱數學競賽 (Mathematics Competition) 已有近百年歷史了，是一個以數學難題挑戰中學生數學智慧的國際性比賽。當中，出數論 (Number Theory) 是出題的一個富源，得運用素因子分解 (Prime Factorization) 、最大公因子 (G.C.D. Greatest Common Divisor 或 H.C.F. Highest Common Factor) 和最小公倍數 (L.C.M. Least Common Multiple) 來作解目工具的題目亦見不少。本文列舉一些本人較喜歡的題目及解法，以供參考。

　

試求不定方程 1/(x + 1) + 1/y + 1/[(x + 1) * y] = 1/1991 的正整數解的組數。(日本數學奧林匹克 1991年)

　

解：已知方程可化為

1991y + 1991(x - 1) + 1991 = (x + 1) * y

(x + 1) * y - 1991(x + 1) - 1991y = 1991

(x + 1) * y - 1991(x + 1) - 1991y + 1991² = 1991 + 1991²

[(x + 1) - 1991] * (y - 1991) = 1991 * 1992

顯然，已知方程的正整數解的個數等於 1991 * 1992 的正因子數目。

再者，1991 * 1992 = 2³ * 3 * 11 * 83 * 161。

即 1991 * 1992 有 (3 + 1) * (1 + 1) * (1 + 1) * (1 + 1) * (1 + 1) = 64 個不同的因子。

故該方程有 64 組正整數解。

　

　

有一個小於 2000 的四位數，它恰有 14 個正因子 (包括 1 和本身)，其中一個素因子的末位是 1。求這個四位數。 (中國上海市初中數學競賽 1984年)

　

解：首先 1 不是素數，所以題中這及的那個末位為 1 的素因子不是 1。

設該四位數為 N。留意 14 = 1 * 14 = 2 * 7，即該四位數可以是只有一個素因子 N = a¹³ 或 含有兩個不同的素因子 N = c * d⁶ 。

但前者是不可能的，因為最小的一個以末位為 1 的素數是 11 ，而 11¹³ 又何止 2000呢。

故是後者，但 d < 3 ，因為 3⁶ * 11 = 729 * 11 = 8019 > 2000。

故得 d = 2，若取 c = 11，得 2⁶ * 11 = 704，不是四位數；取 c = 31，得 2⁶ * 31 = 1984；取 c = 41，得 2⁶ * 41 = 2624 > 2000。

故 N = 1984。

　

欣賞：奧數常以年份入題，但其實以年份作為答案的亦不鮮。

　

　

把 1000000 的每一個真因子取以 10 為底的對數，把這些對數值加起來，得到和 S，求離 S 最近的整數。 (美國數學邀請賽 1986年)

　

解：由於 1000000 = 2⁶ * 5⁶，所以 1000000 有因子 (6 + 1) * (6 + 1) = 49 個。我們把 1000 抽出來，其餘的 48 個因子倆倆一組，每組的乘積為 1000000。

所以所有因子乘積為 1000000²⁴ * 1000 = (10⁶)²⁴ * 10³ = 10¹⁴⁷

但當中 1000000 本身不是真因子，故真因子乘積為 10¹⁴⁷ / 10⁶ = 10¹⁴¹

故 S = log( 10¹⁴¹ ) = 141。

　

　

求所有不超過 100 的恰好有三個正整數因子的正整數的乘積。證明，所有這樣的數是完全平方數。 (墨西哥數學奧林匹克 1990年)

　

解：首先證明所有恰好有三個正整數因子的正整數也是素數的平方。

這類恰好有三個正整數因子的正整數剔除 1 和本身外，還有一個素因子 p。但我們知道 p 不等於 n ，設 n = p * q。若 q 不等於 p ，則 q 也是該數的另一個因子，和三個正整數因子矛盾，故得 p = q，即 n = p²。  

由於超過 100 的素數平方僅有 2²、3²、5² 和 7² 四個，故該乘積為 2² * 3² * 5² * 7² = (2 * 3 * 5 * 7)² = 210² = 44100。所以得證。

　

欣賞：題目利用因子數目為 3便是素數的平方的一個性質，頗為巧妙。其實凡因子數目為奇數也是完全平方數。

　

　

若 r 是 1059, 1417 與 2312 被 d 除後的餘數，這裡 d 是大於 1 的整數，求 d - r 的值。(國際數學奧林匹克候選題 1988年)

　

解：由題目得知 r = 1059 = 1417 = 2312 (mod d)，即 1417 - 1059 = 2312 - 1059 = 0 (mod d)。

故得 895 = 358 = 0 (mod d)，d 為 895 和 358 的公因子，而 (895, 358) = 179。

但由於 179 為素數，故 d 只可取值為 179。

而 1059 = 179 * 5 + 164，即 r = 164，d - r = 179 - 164 = 15。

　

欣賞：本題以同一餘數來引出找公因子的要求，再以素數逼使那找出來的答案只有一個，頗見心思。

　

　

自然數 a₁, a₂, a₃, ... , a₄₉ 的和為 999，令 d 為  a₁, a₂, a₃, ... , a₄₉ 的最大公因子，d 的最大值為多少？ (基輔數學奧林匹克 1979年)

　

解：由於 d = (a₁, a₂, a₃, ... , a₄₉)，即 d 整除 a_i ，其中 i = 1 至 49，即 d 整除  a₁+ a₂ + a₃ + ...  + a₄₉ = 999

另一方面 999 = 3³ * 37。

因為每一個  a_i 均不少於 d，所以 999 不少於 49 d，即 d 一定少於 999 / 49 = 21，故 d 只可為1, 3 或 9。

取最大值 d = 9，可以有 a_i = 9，其中 i = 1 至 48，而 a₄₉ = 567。

　

　

假設 d 為正整數 a 和 b 的最大公因子，而 d' 為 a' 和 b' 的最大公因子。證明數 aa'、ab'、ba' 和 bb' 的最大公因子為 dd'。(匈牙利數學奧林匹克 1913年)

　

解 ：d = (a, b) ，即令 a = xd 及 b = yd 且 (x, y) = 1；同理 d' = (a', b') ，即令 a' = x'd' 及 b' = y'd' 且 (x', y') = 1。

即 (aa' , ab' , ba' , bb') = (dd'xx' , dd'xy' , dd'yx' , dd'yy') = dd' * (xx' , xy' , yx' , yy')。

現在我們得證 (xx' , xy' , yx' , yy') = 1。

假設存在素因子 p 可以整除 xx' , xy' , yx' , yy'，即 p 可以整除 xx' , xy'，但由於 (x', y') = 1，故 p 可以整除 x。

同理考慮 p 可以整除 yx' , yy'，得 p 可以整除 y。即 p 可以整除 x 及 y ，這與 (x, y) = 1 矛盾。故得證 (xx' , xy' , yx' , yy') = 1，即 (aa' , ab' , ba' , bb') = dd'。

　

　

設 [r , s] 表示正整數 r 和 s 的最小公倍數。求有序三元正整數組 (a , b , c) 的個數，其中 [a , b] = 1000，[b , c] = 2000，[c , a] = 2000 。 (美國數學邀請賽 1987年)

　

解：由它們的最小公倍數可知 a, b, c 三數只含 2 和 5 兩個素因子，我們不妨假設 a = 2^x1 * 5^y1，b = 2^x2 * 5^y2，c = 2^x3 * 5^y3 ，而 1000 = 2³ * 5³，2000 = 2⁴ * 5³。

我們得 max(x1, x2) = 3，max(x2, x3) = 4，max(x3, x1) = 4。

由此可知 x3 = 4，而 x1, x2 中必然有一個是 3 另一個不大於 3 ，故一共有七種可能性。

另  max(y1, y2) = 3，max(y2, y3) = 3，max(y3, y1) = 3。

即 y1, y2, y3 中至少有兩個值為 3，而另一個不大於 3，故一共有 10 種能性。

合計滿足上述要求的有序三元正整數組 (a , b , c) 一共有 7 * 10 = 70 個。

　

參考文獻及網址：

中國數學奧林匹克委員會；南開大學數學系  "素因數分解" 及 "公約數和公倍數" 自 世界數學奧林匹克大辭典．數論卷 , 石家莊 : 河北少年兒童出版社 , p. 222 - 305 , 2002