Олимпиада имени Леонарда Эйлера2011-2012 учебный год, I тур регионального этапа

Собственным делителем числа называется любой его натуральный делитель, кроме 1 и самого числа. С составным натуральным числом $a$ разрешается проделывать следующие операции: разделить на наименьший собственный делитель или прибавить любое натуральное число, делящееся на его наибольший собственный делитель. Если число получилось простым, то с ним ничего нельзя делать. Верно ли, что с помощью таких операций из любого составного числа можно получить число 2011? ( С. Берлов )

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.     Ответ. Неверно.
Решение. Покажем, что наибольший простой делитель числа при указанных операциях не уменьшается, и потому мы никогда не получим число 2011 из составного числа, имеющего простой делитель, больший, чем 2011.
Заметим, что наибольший собственный делитель $b$ составного числа $a$ делится на наибольший простой делитель $p$ этого числа. В самом деле, очевидно, $b = a/q$, где $q$ — наименьший простой (и наименьший собственный) делитель числа $a$, и, поскольку $b > 1$, множитель $p$ должен остаться в разложении частного $a/q$ на простые сомножители (если $p = q$, это всё равно верно, поскольку тогда $a = pn$, где $n > 1$). Поэтому если мы делим составное число на его наименьший собственный делитель $q$, то получаем частное $b$ с тем же наибольшим простым делителем $p$. Если же мы к числу $a = bq$ прибавляем кратное $bc$ наибольшего собственного делителя $b$, то получаем число $b(q+c)$, у которого наибольший простой делитель не меньше, чем наибольший простой делитель числа $b$, то есть не меньше $p$.