【附】为便于编辑修改，特提供纯文本文档如下：
一道“五难”数论题的详细剖析与解答
冯跃峰
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αk<aj。
类似地，（x，Sj-1）≠1（否则与aj的最小性矛盾）。
所以，存在1≤i≤k，使pi|Sj-1（∀j≥N 1）……（*）
【差异分析】注意到这里的pi有不同取值（因为x含有的质因数不唯一），与j相关，从而不能说明所有Sj（j≥N 1）有公共质因数。
由此想到，找一个公共的约数p∈{p1，p2，…，pk}，及两个相邻的部分和：Sj、Sj-1，使p|Sj，p|Sj-1（j≥N 1）。这样，便可与（Sj-1，Sj）=1矛盾。
如何找到公共的约数p？这当然要恰当地利用归纳假设——这是本题的第5个难点。
【角色分析】所谓τ=k-1成立，就是所有形如y=p1β1p2β2…pk-1βk-1（βi>0）的正整数都属于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 =x<aj=p1β1p2β2…pk-1βk-1。
所以，归纳假设中所取的正整数y应同时满足：y>x，且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时结论成立。
设τ<k（k≥2）时结论成立，考察τ=k的情形。
假定存在正整数x=p1α1p2α2…pkαkW，必存在正整数N，使n≥N＋1时，an>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时结论成立，命题获证。
,
