Олимпиада имени Леонарда Эйлера2010-2011 учебный год, IV тур дистанционного этапа

Три натуральных числа $a$, $b$, $c$ подобраны так, что $\text{НОД}(ab, c) = \text{НОД}(a, bc)$. Докажите, что после сокращения дроби $a/c$ получится несократимая дробь, числитель и знаменатель которой взаимно просты с $b$.

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

Комментарии от администратора Комментарии от администратора №1.     Решение. Достаточно доказать, что любое простое число $p$, входящее в разложение на простые множители числа $b$, входит в разложение числа $a$ и $b$ разложение числа $c$ в одинаковых (возможно, нулевых) степенях. Докажем это. Действительно, пусть, например, в разложение числа $a$ входит больше множителей $p$, чем в разложение числа $c$. Тогда в разложение числа $\text{НОД}(ab,c)$ число $p$ входит с тем же показателем, что и в число $c$. А в $\text{НОД}(a, cb)$ входит с большим показателем, потому что и в числе $a$ и $b$ числе $cb$ больше множителей $p$, чем в числе $c$. Аналогично разбирается второй случай.