|
|
 |
Условие
Возрастающая последовательность натуральных чисел $a_1 < a_2 < \dots$ такова, что при каждом целом $n > 100$ число $a_n$ равно наименьшему натуральному числу, большему чем $a_{n-1}$ и не делящемуся ни на одно из чисел $a_1, a_2, \dots, a_{n-1}$. Докажите, что в такой последовательности лишь конечное количество составных чисел.Решение 1
Пусть последовательность $S$ из условия задачи содержит бесконечно много составных чисел. Так как члены с номерами больше 100 не делятся на другие члены последовательности, она не содержит 1.Пусть $p_1,p_2,\dots, p_k$ – все простые числа, не превосходящие $a_{100}$. Все остальные простые числа входят в $S$: действительно, пусть $q$ – одно из них, и пусть $a_t$ – наибольшее число в последовательности, меньшее чем $q$. Тогда $q$ больше $a_1,\dots, a_t$ и не делится на них (так как единицы среди них нет), причём меньшего числа с такими свойствами не существует. Следовательно, $a_{t+1}=q$.
Никакой другой член исходной последовательности не делится на $q$: предыдущие меньше $q$, а последующие не делятся на члены с меньшими номерами. Следовательно, составные числа из $S$ не имеют простых делителей кроме $p_1,\dots, p_k$.
Дальше возможны два способа решения.
Первый способ. Пусть $1\le i\le k$, и пусть $r=p_i^{d_i}$ – наименьшая степень числа $p_i$, которая больше $a_{100}$. Если $S$ не содержит меньшей степени $p_i$, то $r$ не делится на меньшие числа из $S$ и потому содержится в $S$. Таким образом, для каждого из чисел $p_1,\dots,p_k$ некоторая его степень содержится в $S$. Пусть $P$ – произведение всех этих степеней. Если в $S$ есть составное число $m$, большее чем $a_{100}$, то оно не делится на эти степени и на остальные простые числа, поэтому $m\le P$.
Второй способ. Пусть $S_0$ – совокупность всех составных чисел из $S$, имеющих номера больше 100. Предположим, что $S_0$ бесконечно. Пусть $m_1$ – наименьшее число из $S_0$. Любое другое число из $S_0$ не делится на $m_1$, поэтому какое-то $p_i$, где $1\le i\le k$, входит в его разложение с меньшим показателем, чем в разложение $m_1$. Для некоторого $i$ количество таких чисел бесконечно, а среди них бесконечно много таких, что в их разложении показатель при $p_i$ одинаков. Совокупность таких чисел обозначим $S_1$.
Дальше рассуждаем аналогично: пусть $m_2$ – наименьшее число из $S_1$, тогда любое другое число из $S_1$ не делится на $m_2$, и т.д. Получаем бесконечное множество чисел из $S_1$, в разложении которых одинаков показатель при некотором $p_j$ ($j\ne i,\ 1\le j\le k$). Это бесконечное множество обозначим $S_2$, и т.д.
В итоге получаем бесконечное множество $S_{k-1}$ членов исходной последовательности, у которых номера больше 100, а разложения отличаются показателем лишь при одном простом множителе. Но если $n_1,n_2$ – два числа из $S_{k-1}$ и этот показатель больше у $n_1$, то $n_1$ делится на $n_2$ и они не могут одновременно принадлежать исходной последовательности – противоречие. (В действительности $S_k$ можно построить по тому же правилу, и получится бесконечное множество, в котором все числа на самом деле равны.)
