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

Даны натуральные числа $a$ и $b$, причем $a < 1000$. Докажите, что если $a^{21}$ делится на $b^{10}$, то $a^2$ делится на $b$. ( П. Кожевников )

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

Комментарии от администратора Комментарии от администратора №1.     Решение. Предположим, что утверждение задачи неверно; тогда найдётся простое число $p$, входящее в разложение числа $a^2$ на простые множители с показателем меньшим, чем в разложение числа $b$. То есть, если $a$ делится на $p^k$, но не делится на $p^{k+1}$, а $b$ делится на $p^m$, но не делится на $p^{m+1}$, то $m > 2k$, а значит, $m \geq 2k + 1$. Но из делимости $a^{21}$ на $b^{10}$ следует, что $21k \geq 10m$. Отсюда $21k \geq 10(2k + 1)$, то есть $k \geq 10$. Но $a < 1000 < 2^{10} \leq p^{10} \leq p^k$, поэтому $a$ не может делиться на $p^k$. Противоречие.