ВсОШ 2024, 9 класс, задача 2
У натурального числа ровно делителей. Может ли оказаться, что никакая разность двух различных его делителей не делится на ?
Ответ. Нет.
Решение. Предположим, что такое число существует. Условие равносильно тому, что все числа, образованные последними двумя цифрами делителей, различны (мы считаем, что к однозначным числам спереди приписаны нули). Назовём такую пару последних цифр хвостом числа. Заметим, что хвост числа имеет те же остатки от деления на и на , что и исходное число.
Предположим, что делится на . Тогда для любого его делителя , не кратного , существует и делитель , кратный . При этом для разных делителей мы получаем разные делители ; поэтому количество кратных делителей не меньше половины, то есть не меньше . Но такие делители имеют хвосты, оканчивающиеся либо на , либо на . Таких возможных хвостов не больше , поэтому два из них совпадают. Это противоречие показывает, что не делится на , и хвосты его делителей не могут оканчиваться на или .
Если число нечётно, то все его делители также нечётны. Однако существует всего возможных нечётных хвостов, и из них оканчиваются на , то есть не могут появиться. Поэтому и в этом случае найдутся два одинаковых хвоста.
Если число делится на , но не на , то все его делители разбиваются на пары , где - нечётный делитель . При этом все числа вида имеют хвосты, не делящиеся на , а таких хвостов (не делящихся на ) всего . Значит, два из этих хвостов одинаковы.
Наконец, пусть наибольшая степень двойки, на которую делится , равна , где . Тогда, если - нечётный делитель , то числа также будут делителями , и этим исчерпываются все делители . Поэтому общее число делителей будет кратно . Таким образом, делится на и, значит, .
Тогда имеет нечётных делителей и столько же делителей, которые чётны и не делятся на четыре. Стало быть, оставшиеся делители (которых не меньше ) кратны и, значит, их хвосты также кратны четырём. Но таких хвостов возможно лишь , поэтому опять два из них совпадут.