素數與奧數
數學奧林匹克 (Mathematical Olympiad) 也稱數學競賽 (Mathematics Competition) 已有近百年歷史了,是一個以數學難題挑戰中學生數學智慧的國際性比賽。當中,出數論 (Number Theory) 是出題的一個富源,與素數 (Prime Number) 相關的題目亦見不少。本文列舉一些本人較喜歡的題目及解法,以供參考。
求所有素數 p, 使 4p2 +
1 和 6p2 + 1也是素數。(波蘭數學競賽 1964年)
解:設 p = 5k + r 、u = 4p2 + 1 及 v = 6p2 + 1。
則 u = 100k2 + 40kr + 4r2 + 1,而 v = 150k2 + 60kr + 6r2 + 1。
若 p = r = 0 (mod 5),即 u = 1 (mod 5) 且 v = 1 (mod 5)。
若 p = r = 1 (mod 5),即 u = 0 (mod 5) 且 v = 2 (mod 5)。
若 p = r = 2 (mod 5),即 u = 2 (mod 5) 且 v = 0 (mod 5)。
若 p = r = 3 (mod 5),即 u = 2 (mod 5) 且 v = 0 (mod 5)。
若 p = r = 4 (mod 5),即 u = 0 (mod 5) 且 v = 2 (mod 5)。
顯然 u 和 v 不可能是 5,故 u = 0 (mod 5) 或 v = 0 (mod 5) 代表這兩數是合數。
但 p 可以為 5,當 p = 5 時,u = 101 而 v = 151 均為素數,故 p = 5 是唯一的解。
欣賞:本題技巧在於把素數 p 按模五作分類,利用同餘式的計算來剔除不可能的答案。
求
三個素數,使得它們的積為它們的和的 5 倍。(基輔數學奧林匹克 1973年)
解:設該三個素數為 p、q、r 。
我們得 p * q * r = 5 * (p + q + r)。因而 p、q、r 中必有一個等於 5,我們不妨設 r = 5。
簡化後得 p * q = p + q + 5,即 (p - 1) * (q - 1) = 6。
故我們得 (p-1 , q-1) = (1 , 6)、(2 , 3)、(3 , 2)、(6 , 1),
即 (p , q) = (2 , 7)、(3 , 4)、(4 , 3)、(7 , 2)。
因為 4 不是素數,故該三個素數是 2、5、7
欣賞:本題利用恆等式 pq - p - q = (p - 1) * (q - 1) + 1,同理 pq + p + q = (p + 1) * (q + 1) - 1。
各網友亦可試把上題中的 5 倍改為 7倍,看看又有什麼發現。
設 K
是這樣的自然數的全體,其中每一個數由 0 與 1 兩個數字相間而成,首位和末位都是 1,問 K 中有多少個素數?(美國波特蘭數學競賽 1989年)
解: 1 不是素數,101 是素數。
若 101010...01 中有 3 個或以上的 1 時,則該數可以寫成
1 + 100 + 1002 + ... + 100n
= (100n + 1 - 1) / (100 - 1)
= (102n + 2 - 1) / (102 - 1)
= [(10n + 1 + 1) * (10n + 1 - 1)] / [(10 + 1) * (10 - 1)]
= [(10n + 1 + 1) * 999...9] / [(10 + 1) * 9]
= [(10n + 1 + 1) * 111...1] / (10 + 1)
當 n 為奇數時,n + 1 為偶數,即 111...1 / 11 為大於 1 的整數,連同 (10n + 1 + 1) 也是大於 1 的整數,故上式為合數。
當 n 偶奇數時,n + 1 為奇數,11 可整除 (10n + 1 + 1),而其商為一大於 1 的整數,連同 111...1 也是大於 1 的整數,故上式為合數。
因此 K 中只有一個素數,即 101。
欣賞:由於素數沒有固定的特性,所以這一類數列中的素數問題,通常在一臨界的第 n 項以後,全為合數。至於在臨界的第 n 項以前有多少個素數,則要一一測試了。
證明或說明不正確,存在素數 a,
b, c, d,且 a < b < c < d,滿足 1 / a + 1 / d = 1 / b + 1 / c。(新加坡數學競賽 1987年)
解:利用反證法,先假設結論正確,得 cd (b - a) = ab (d - c),但因為 b、c、d 均為素數,故得 b 整除 (b - a)。
即 b 整除 a,這與 a, b 為兩個不同的素數矛盾,故結論不正確。
證明對於一切整數 n, n2 +
2n + 12不是 121 的倍數。(加拿大數學競賽 1971年)
解:利用反證法,先假設相反結論,即對於某整數 n, n2 + 2n + 12是 121 的倍數。
即 n2 + 2n + 12 = (n + 1)2 + 11 = 121k,其中 k 為正整數。
即 (n + 1)2 = 121k - 11 = 11(11k - 1)
由於 11 為素數,故 11 整除 (n + 1),即 121 整除 (n + 1)2 ,得 11 整除 (11k - 1),矛盾。
故得證。
欣賞:證明「不是什麼什麼」,常用反證法。當然也可以把 n 按模 121 分類,一一測試其對應的 n2 + 2n + 12 模 121 的值為多少,看看有否有為零的。
對分數 1/1, 1/2,
1/3, ..., 1/(p - 2), 1/(p - 1) 通分並求和,證明如果 p 是大於 2 的素數,那麼所得和數的分子可以被 p
整除。(全俄數學奧林匹克 1986年)
解:若 p 是大於 2 的素數,即 p 是奇素數,p - 1 是偶數。
所以 1/1 + 1/2 + 1/3 + ... + 1/(p - 2) + 1/(p - 1)
= [1/1 + 1/(p - 1)] + [1/2 + 1/(p - 2)] + [1/3 + 1/(p-3)] + ...
= p/[1 * (p - 1)] + p/[2 * (p - 2)] + p/[3 * (p - 3)] + ...
= p*k / (p-1)! 其中 k 為某正整數。
由於 p 是素數,即 p 與 (p - 1)! 互素,故所得和數的分子可以被 p 整除。
欣賞:本題技巧在於把級數首尾項列為同一組,分組求和。
(1) 是否存在 14
個連續正整數,其中每一個均至少可被一個不少於 2,不大於 11 的素數整除?
(2) 是否存在 21 個連續正整數,其中每一個均至少可被一個不少於 2,不大於 13 的素數整除? (美國數學奧林匹克 1986年)
解:(1) 不存在。以下會用反證法作證明。
設該 14 個連續正整數為 N, N + 1, N + 2, ... , N + 13。
由於對稱性,不妨設 N 為偶數,於是 N, N + 2, N + 4, ... , N + 12 均可被 2 整除。
而餘下的七個數,即 N + 1, N + 3, N + 5, ... , N + 13 可被 3, 5, 7, 11 整除的最多個數分別為 3個、2個、1個、1個,總和也是 7 個。
所以素數 3, 5, 7, 11 均必須分別整除它們各自的可能整除的最多個數的數,且不會有兩個不同的素數整除同一個數的情況發生。
由於被 3 整除的奇數須相隔 6 個數,又恰有 3 個,故可為
N + 1, N + 7, N + 13
而被 5 整除的奇數須相隔 10 個數,又恰有 2 個,故可為
N + 1, N + 11 或 N + 3, N + 13
即無論任何情況,總有一個數同時被 3 及 5 整除,這數是 N + 1 或 N + 13。這使上述假設不能成立。
(2) 存在。我們留意到自 - 10 至 + 10 的 21 個連續數中,除 +1 或 -1 外,其餘的每一個數均至少可被 2, 3, 5, 7 之一整除。
現我們設法以 11 和 13 這兩個素數來解決這兩個數。
即要求 N = 2 * 3 * 5 * 7k 及 N= 11m + 1 及 N = 13n - 1 ,這是一道中國剩餘定理 (Chinese Remainder Theorem) 的問題。
我們知道這樣的 N 是存在的,如 99540,即 99530 至 99550 間這 21 個連續正整數符合題目的要求。
參考文獻及網址:
中國數學奧林匹克委員會;南開大學數學系 "素數與合數" 自 世界數學奧林匹克大辭典.數論卷 , 石家莊 : 河北少年兒童出版社 , p. 159 - 221 , 2002