Эйлер атындағы олимпиада, 2011-2012 оқу жылы, аймақтық кезеңнің 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$.