素數與奧數

數學奧林匹克 (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