【原】初中竞赛题选讲 第四百五十五题解答

本题目选自 2021北欧数学奥林匹克 

黑板上写有若干个大于的整数. 诺迪对其进行如下操作: 在每一步中, 诺迪在黑板上写下满足如下条件的最小整数:
这个数比黑板上已有的每个数都大.
黑板上已有的每个数都不能整除这个数.
求证: 在某一步之后, 诺迪写下的全是素数.

证明: 设初始时黑板上最大的整数为.
诺迪写下的整数为:
我们首先证明, 任意一个大于的素数,必然会出现在黑板上.
反证: 假设素数未出现在黑板上, 由于数列为单增的无穷数列, 则必存在正整数, 使得
注意到我们写下之后，满足诺迪要求的两个条件, 且比小, 故不为满足条件的最小整数, 矛盾!

于是假设不成立, 即任意一个大于的素数,必然会出现在黑板上.
对任意合数, 若存在素数使得, 由于, 可能需要些时已经出现在了黑板上, 故必不可能出现在黑板上.
于是对任意黑板上出现的合数, 它的所有素因子一定小于.

下面我们证明一个引理:

引理: 给定自然数, 已知为素数.无穷数列中每个数都不含之外的素因子. 则必存在正整数,使得.

引理的证明: 对进行归纳.时,显然满足条件.

对数列, 若存在正整数, 使得对任意的自然数, 均有,则必存在正整数, 使得,的正整数有无穷多个. 此时转化为个素因子的情况, 由归纳原理知显然成立.

反之, 若满足的正整数有无穷多个.

则对这无穷多个数组成的新数列, 再考虑满足的正整数是否有无限个. 若为有限个, 则由归纳原理知结论成立.

若为无限个, 继续考虑这满足条件的数组成的无穷项的新数列....

若每一步均为无限个, 则我们必可以得到一个正整数, 使得对任意,均有, 此时为的倍数.

引理证毕.

回到原题目, 由于对任意黑板上出现的合数, 它的所有素因子一定小于, 故这些合数所组成的数列的素因子个数为有限个. 由引理知, 若这些合数为无穷个, 则必存在倍数关系. 于是这样的合数只有有限个. 当这有限个合数被列举完之后, 再列出的正整数必为素数.

证毕.