ВсОШ 2023, 9 класс, задача 4
( баллов) Даны натуральные числа , и . Ни одно из них не кратно другому. Известно, что число делится на . Докажите, что .
(М. Антипов)
Ответ
Первое решение. Предположим противное: пусть . Из делимости на следует, что число кратно . Поскольку числа и взаимно просты, получаем, что делится на . Ясно, что , поэтому либо , либо .
В первом случае получаем и, значит, делится на , что невозможно по условию. Во втором случае имеем
то есть . Это значит, что , то есть ; но это также невозможно по условию, ибо тогда снова делится на .
Второе решение. Опять же предположим противное. Поскольку делится на , то и тоже кратно , то есть при некотором натуральном . Иначе говоря,
Значит, делится на .
По нашему предположению, . С другой стороны, поскольку (иначе делится на ), имеем
откуда . Значит, , и потому .
Теперь переписывается в виде , то есть . Но тогда , то есть делится на . Это невозможно.
Доказано, что или делится на .