初等數論題大全（一道五難數論題的詳細剖析與解答）

2023-05-09 15:36:28

【附】為便於編輯修改，特提供純文本文檔如下：

一道「五難」數論題的詳細剖析與解答

馮躍峰

2018年全國高中數學聯賽加試中，有一道個人認為是質量非常高的數論題，題目如下：

數列{an}定義如下：a1是任意正整數，an 1是與Σi=1nai互質，且異於a1，a2，…，an的最小正整數。試證：每個正整數都在數列{an}中出現。（2018高中數學聯賽加試第4題）

本題有較大的難度，我們稱之為「五難」問題——至少有5個難點。

說其難，並非是它涉及什麼高深的數論知識背景，而是指思維層面上一些作法難於想到。相反地，本題幾乎無需用到數論中的相關定理。

本文的目的，就是發掘本題在突破這些難點上的獨特思路及相應的處理手法。

首先，從目標看，即使是取一個具體的數，比如2018，你也無從判斷它是否屬於W（數列{an}各項組成的集合）。

本題的獨特之處就在於：證某個具體的正整數出現在題給數列W中卻很困難，而證所有正整數出現在數列W中則反而可行（以面帶點）！因為我們有一個強有力的工具：數學歸納法——在歸納假設（某個數屬於W）的前提下，可順利推出下一個數也屬於W，這是解題的第一個難點。

其次，從條件看，直接對n歸納是不可取的，因為「正整數n屬於W」與「正整數n 1屬於W」之間並沒有遞推關係，題中給出的遞歸是an 1與前n項a1，a2，…，an之間的聯繫，無法直接用於判斷「正整數n 1也屬於W」。

應對誰進行歸納？題中並沒有更多的歸納對象可供選擇，這是第二個難點，這也是本題最關鍵的難點之一。

實際上，我們不能對正整數一個個歸納，只能對正整數的某種屬性歸納（分批歸納，同一屬性批次含多個正整數）。

應考察正整數的什麼屬性呢？不妨取一個具體的數列{an}來研究，從中發現與「遞歸」相關的性質。

【研究特例】取a1=1，則易知數列前若干項為：

1，2，4，3，7，5，9，…

該序列各項之間似乎沒有什麼聯繫，但這些項卻有一個共同點，你發現了嗎？——可考察其標準分解式。

【發掘規律】這些數都只含有一個質因數，為pα形式的數。

它啟發我們產生這樣的設想：對於只含有一個質因數的正整數pα，可以統一於一個批次中一次性證明其都屬於W。

由此想到所選擇歸納對象是：正整數n的質因數個數——突破本題最大的難點。

【分批歸納】對正整數含有質因數的個數τ進行歸納。

當τ=1時，正整數為pα形式，我們證明任何pα形式的數都在數列中。

要證明pα∈W，可想像pα=aj。這自然想到驗證pα滿足aj定義中的「三性」：

（1）互異性：aj異於a1，a2，…，aj-1；（2）互素性：（aj，Sj-1）=1；（3）最小性：aj是滿足（1）（2）的最小正整數。

但數列{an}及pα都沒有具體給定，難以從正面找到合乎（1）（2）（3）的正整數j，只能從反面行驗證某個條件「不滿足」，由反設「pαW」，導出矛盾。——這是本題的第三個難點。

【反面思考】反設pαW，則顯然pα滿足（1），所以pα不能同時滿足（2）和（3）。

這能產生怎樣的「有用信息」呢？它還非常隱蔽，很難進一步推理。——這是本題的第四個難點，也是本題的另一個關鍵之處。

儘管不能直接由「pα不能同時滿足（2）和（3）」導出相關結論，但也可以看出一些端倪。比如，我們期待pα不滿足（2），即（pα，S j-1）≠1，因為由此可得出p|S j-1（有用信息）。

現在麻煩的是，我們不能先讓pα滿足（3），因為滿足（3）是以滿足（1）（2）為前提的。所以，我們期待適當選取關聯對象aj，由aj滿足（3）來「倒逼」pα不滿足（2），這是本題的另一個最難之處。

為利用aj的「最小性」，想到取pα<aj。因為這樣一來，pα比aj更小，再「嵌入」一個「反證法」（反設pα滿足（2））則可導出與aj的「最小性」矛盾。

【關聯性質】取數列中的一個項aj，使pα<aj，則有（pα，Sj-1）≠1（產生有用信息），否則與aj的最小性矛盾。

現在的問題是，這樣的aj存在嗎？回答是肯定的，利用數列的無限性即可。

【反面剔除】因為不超過pα的正整數只有有限個，必定存在正整數N，使j≥N 1時，恆有pα<aj。

取j=N 1，可知（pα，SN）≠1，否則與aN 1的最小性矛盾，所以p|SN。

取j=N 2，類似可知，（pα，SN 1）≠1，即p|SN 1。

但（SN 1，SN）=（SN 1­-SN，SN）=（aN 1，SN）=1，與p是「公約數」矛盾。

所以，τ=1時結論成立。

值得指出的是，此處的歸納法，「奠基」比「遞推」更難。完成了奠基，後面的遞推就非常順暢了，幾乎與前面的推理類似，當然需稍作優化（還有最後一個難點）。

設τ<k（k≥2）時結論成立，考察τ=k的情形。

與τ=1時類似，難以從正面證明相應的正整數屬於W，宜從反面入手。

【平凡拓廣】反設存在正整數x=p1α1p2α2…pkαkW（這裡αi是正整數，以保證x含有k個不同質因數），取關聯條件：設正整數j，滿足x<aj，則必有（x，Sj-1）≠1，否則與aj的最小性矛盾。

【反面剔除】同樣，因為不超過x=p1α1p2α2…pkαk的正整數只有有限個，必定存在正整數N，使j≥N 1時，恆有x=p1α1p2α2…pkαk0）的正整數都屬於W，取其中一個y=p1β1p2β2…pk-1βk-1=aj。

這裡取定的j，假定能使前面的（*）式仍然成立，這也只需j滿足x=p1α1p2α2…pkαk<aj，即j≥N 1。

對這樣的j，仍存在1≤i≤k，使pi|Sj-1。但由數列定義，（aj，Sj-1）=1，這表明pi（1≤i≤k-1）都不能是Sj-1的約數。

由此可見，滿足「pi|Sj-1」中的pi不能是p1，p2，…，pk-1之一，只能是剩下的唯一質因子pk，它便是我們要找的作為公共質因子p。

【目標轉換】這樣，子目標變為：存在j≥N 1，使pk|Sj，pk|Sj-1。

對上面選定的j（y∈W推得y=aj），並未保證j≥N 1，需要優化。

【優化假設】顯然，為保證j≥N 1，只需y=aj異於a1，a2，…，aN。

此外，（*）中的「pi|Sj-1」是由「x<aj」推得的，為了存在1≤i≤k，使pi|S j-1，必須x<aj，即p1α1p2α2…pkαk =xx，且y異於a1，a2，…，aN（以保證j≥N 1），這兩點能否同時做到？——類似進行反面剔除即可。

【反面剔除】注意到y的「表達式」中的指數βi（1≤i≤k-1）可任意大，從而y=p1β1p2β2…pk-1βk-1可任意大，取y=aj>x，且y=aj異於a1，a2，…，aN是可行的。

對於上述「優化」選定的y=aj，有aj>x，且j≥N 1。

但x異於a1，a2，…，aj-1（因為x不屬於W），所以（x，Sj-1）≠1（否則與aj的最小性矛盾），即存在1≤i≤k，使pi|Sj-1。

進一步，j 1≥N 1，且aj>x，對上述取定的j，又存在存在1≤t≤k，使pt|Sj。

由數列定義，有（aj，Sj-1）=1，進而有，（aj，Sj）=（aj，Sj-aj）=（aj，Sj-1）=1。

再注意到aj= y=p1β1p2β2…pk-1βk-1含有質因數p1，p2，…，pk-1，所以Sj、Sj-1都不含質因數p1，p2，…，pk-1。只能是i=t=k，即pk|Sj-1，pk|Sj。

但（Sj，Sj-1）=（Sj-Sj-1，Sj-1）=（aj，Sj-1）=1，矛盾。

【新寫】設數列{an}各項組成的集合為W，我們證明任何正整數都屬於W。對正整數所含質因數個數τ歸納。

當τ=1時，假定存在pαW，因為不超過pα的正整數只有有限個，必存在正整數N、N 1，使pα< aN 1，pα< aN 2。

易知（pα，SN）≠1，否則與aN 1的最小性矛盾，所以p|SN。同理，p|SN 1。

但（SN 1，SN）=（SN 1­-SN，SN）=（aN 1，SN）=1，矛盾。

所以，τ=1時結論成立。

設τx。於是（Sn-1，x）≠1，否則與an的最小性矛盾（xW當然異於a1，a2，…，an-1，但x更小）。於是，存在1≤i≤k，使pi|Sn-1（∀n≥N＋1）。（*）

由歸納假設，形如p1β1p2β2…pk-1βk-1的數都屬於W，這樣的數有無窮多，可取正整數aj=p1β1p2β2…pk-1βk-1，使aj異於a1，a2，…，aN（即j≥N＋1），且aj>x。

但x異於a1，a2，…，aj-1（因為x不屬於W），所以（x，Sj-1）≠1（否則與aj的最小性矛盾），即存在1≤i≤k，使pi|Sj-1。

進一步，j 1≥N 1，且aj 1>x，對上述取定的j，又存在存在1≤t≤k，使pt|Sj。

由數列定義，（aj，Sj-1）=1，進而（aj，Sj）=（aj，Sj-aj）=（aj，Sj-1）=1，並注意到aj= y=p1β1p2β2…pk-1βk-1含有質因數p1，p2，…，pk-1，所以Sj、Sj-1都不含質因數p1，p2，…，pk-1。只能是i=t=k，即pk|Sj-1，pk|Sj。

但（Sj，Sj-1）=（Sj-Sj-1，Sj-1）=（aj，Sj-1）=1，矛盾，故τ=k時結論成立，命題獲證。