Делимость и делители (множители)

Обозначим указанную сумму за Тогда, так как для каждого число — также делитель,

Следовательно, складывая исходное и последнее выражение для умноженные на получаем

При этом — количество делителей числа — вычисляется по формуле

( каждый из простых множителей может входить в делитель в любой степени от до своей степени вхождения в число ). Таким образом,

Запишем равенство в следующем виде: Если мы докажем, что НОД и равен то тогда будет кубом. Предположим, что в этой ситуации не является кубом. Тогда в разложение входит какое-то простое число в степени, не кратной Скобка на не делится, значит входит в в степени, не кратной чего быть не может.

Итак, докажем взаимною простоту и Ясно, что НОД этих чисел равен НОДу и предположим, что этот НОД равен Тогда делится на Пусть делится на некоторое простое число тогда на делится и Значит, также делится на Также делится на а значит и на Получается, что НОД и больше противоречие. Значит, НОД и равен что и требовалось.

Для начала разберемся, какие простые множители входят в число и в каких степенях.

Теперь рассмотрим вид числа, которое является делителем и которое само делится на Пусть делится на тогда

где все принимают значения от до соответствующей степени в числе кроме которое принимает значения от до .

Следовательно, исходная задача свелась к подсчету различных чисел определенного вида. Посчитаем количество таких различных

Утверждается, что удовлетворяет условию задачи, если и только если его разложение на простые множители имеет вид либо , либо .

Действительно, для каждого имеется делителей числа , содержащих в степени в разложении на простые множители: все эти делители имеют вид . Следовательно, произведение всех делителей числа содержит в степени . Условие, что произведение всех делителей равно , эквивалентно утверждению, что каждое входит в их произведение в степени , и, тем самым, предыдущее выражение равно . Другими словами,

С другой стороны, . Отсюда следует, что . Пусть . Тогда одно из , скажем, равно 1 , а тогда (простота числа 5). В случае, когда , получаем уравнение , то есть . Итак, все числа , удовлетворяющие условию задачи, имеют разложение на простые множители вида либо , либо . Перечислим те из них, которые лежат между 400 и 600.

Числа . Имеем , тем самым, . Итак, . Следовательно, , а, значит,

Выписывая всевозможные произведения , лежащие в промежутке от 400 до 600 , с вышеуказанными и , получаем .

Единственное , лежащее между 400 и 600 , есть . Итого получаем список всех возможных чисел :

Заметим, что десятичная запись числа оканчивается на Кроме того, это число делится на все степени двойки с показателями от до Следовательно, число составленное из последних цифр в записи должно делиться на

Рассмотрим число, составленное из двух последних цифр в десятичной записи числа Если число — убывающее, то это или Но числа вида или не делятся на а число вида (других цифр впереди быть не может) делится на а на не делится. Следовательно, число составленное из двух последних цифр, это

Рассуждая аналогично для чисел, составленных из трёх, четырёх, пяти и шести последних цифр, получим, что число должно оканчиваться на Это число не делится на поэтому не может быть степенью а число не делится на Значит, чисел, удовлетворяющих условию задачи, не существует.

Пусть где — простое число. Это означает, что одно из чисел и делится на Разберем оба случая.

Предположим для начала, что Тогда Но, поскольку мы можем написать цепочку неравенств

Перейдём к случаю После преобразований получаем равенство Если для какого-то натурального числа то и, следовательно, то есть или В качестве можно взять само число Получаем, что либо что, очевидно, невозможно, так как в все простые сомножители входят хотя бы в третьей степени; либо В последнем случае получаем, что

и, так как — простое число, необходимо Тогда и

Пусть первое из чисел равно тогда сумма арифметической прогрессии этих подряд идущих чисел равна

что эквивалентно

Поскольку чётно, то скобки имеют разную чётность, следовательно, чётна ровно одна из них.

Если чётно, то при этом но из условия на произведение получаем противоречие.

Значит, нечётно и является делителем то есть может быть равно Легко видеть, что и каждое чётное значение можно получить выбором потому при решение относительно есть всегда, откуда все найденные подойдут.

Рассмотрим степени двойки, на которые делятся выписанные числа; пусть — наибольшая из них. Если хотя бы два выписанных числа делятся на то два соседних таких числа будут различаться на Значит, одно из них делится на что невозможно в силу выбора Следовательно, среди выписанных чисел ровно одно делится на

Наименьшее общее кратное группы, содержащей это число, будет делиться на а НОК оставшейся группы — не будет. Значит, сумма этих НОК не делится на с другой стороны, эта сумма больше чем Поэтому эта сумма не может быть степенью двойки.

Пусть Сашино число имеет делители Заметим, что число взаимно просто со всеми этими делителями, поэтому число должно делиться на При этом и так далее Перемножив эти неравенства, получим, что делимое не превосходит своего делителя, а это возможно только в том случае, когда все неравенства обращаются в равенства. Но тогда т. е. делится на Значит, либо либо числа не существует и

Предположим, что делители можно расположить в прямоугольную таблицу Пусть сумма чисел в каждом столбце равна Поскольку находится в одном из столбцов, равенство достигается при

Для всех определим как максимальное число в -м столбце. Не умаляя общности, положим Эти числа — делители значит Поскольку — максимальное число в -м столбце, имеем

Таким образом, откуда Учитывая, что получаем Значит, все ранее полученные неравенства становятся равенствами. В частности, и в этом случае все условия соблюдены.

Разложим на простые множители Обозначим НОД наших чисел через Тогда откуда Наибольшее натуральное число, не превосходящее делящее это

Осталось привести пример, что НОД чисел действительно может быть равен Подходят числа

Первое решение.

По условию число имеет вид где — нечётное. Заметим, что любому нечётному делителю числа взаимнооднозначно соответствует группа чётных делителей

Тогда если обозначить Митину сумму через то Ванина сумма примет вид

Если перемножить суммы, то мы получим

Теперь видно, что вопрос задачи сводится к тому, может ли быть квадратом число вида Очевидно, что нет, потому что оно делится на но не делится на

Второе решение.

Разложим число из условия по основной теореме арифметике

Из такого представления известно, что сумма всех делителей числа равна

При этом это является суммой всех нечётных делителей Для получения суммы только чётных делителей формула принимает вид

В итоге произведение сумм равно однако легко видеть, что в левую часть двойка входит в нечётной степени, потому сумма не может быть точным квадратом.

За выражение произведения в виде S² * (2 + 2² + … + 2^k) – не менее 2 баллов. 

Пусть они не взаимно простые. Тогда и имеют общий простой делитель Рассмотрим произведение чисел и и преобразуем

Тогда произведение тоже делится на Но поскольку число является собственным делителем какого-то из чисел или что противоречит их простоте.

Cреди восьми последовательных натуральных чисел найдутся числа, дающие остатки и при делении на Они делятся на но не делятся на так что они обязаны иметь вид и Тогда то есть что невозможно. Противоречие.

Пусть — почтенное число. Тогда сумма его делителей, отличных от равна У числа заведомо есть делители

Все они различны и отличны от а их сумма равна

Следовательно, у числа нет делителей(так как оно тоже должно быть почтенным), отличных от вышеперечисленных. Это означает, что является степенью простого числа. В противном случае, если делится на (и не делится на ), то в приведённом выше списке делителей числа отсутствует делитель
Итак, пусть Тогда сумма отличных от делителей числа равна что по условию равно Но

что меньше при и равно при Таким образом, числа удовлетворяют условию задачи, а остальные числа не удовлетворяют условию.

Если то делится на Поэтому можно считать, что тогда
Пусть сумма чисел равна а сумма чисел равна По условию делится на Обозначим их отношение через покажем, что Действительно,

(последний переход несложно проверить), и значит, Поскольку получим равенство или, что то же самое,

Если не делится на , т.е. то и значит, Проверим, что на самом деле выполнено неравенство т.е. что число не может быть слишком крупным отрицательным числом. Действительно, и и поэтому Тогда

Здесь как раз применяем, что В итоге, противоречие.

Пусть — наибольший делитель числа меньший, чем Тогда где — наименьший простой делитель числа Имеем Число в правой части не делится на поэтому Отсюда следует, что нечётно, а тогда и нечётно. Поскольку делится на

Если то что невозможно, так как делится на то есть не является простым. Значит, число кратно и потому

Если то откуда и

Если же то и число делится на что невозможно.

Ясно, что все принадлежат интервалу и различны, поскольку если то откуда что неверно по условию задачи.

Еще заметим, что каждое число, не делящееся на из интервала совпадает с одним из Действительно, пусть и не делится на Тогда либо либо Тогда одно из чисел совпадает с откуда получаем, поскольку , что Тогда получаем, что множество всех совпадает с множеством всех чисел из интервала не делящихся на

Пусть — максимальная степень тройки, делящая Поскольку имеем Пусть где не делится на Заметим, что все лежат в интервале поскольку и, следовательно Докажем, что все различные. Предположим противное: для некоторых Мы знаем, что поэтому Пусть Тогда

С другой стороны,

Таким образом, мы получаем противоречие, и для всех Докажем теперь, что любое число, не делящееся на из интервала совпадает с одним из Действительно, пусть Тогда существует такое что следовательно, и при этом Тогда при некотором Но тогда откуда

Итак, множество всех чисел совпадает с множеством всех чисел, не делящихся на в интервале поэтому совпадает с множеством

Тогда имеем

что и требовалось.

Пусть Обозначим исходные числа (в порядке обхода) через мы будем считать, что Положим Предположим что числа — это подряд идущих натуральных чисел.

Рассмотрим наибольшую степень двойки на которую делится хотя бы одно из чисел Заметим, что ни одно из чисел не делится на Пусть для определённости тогда и Значит, и при некоторых нечётных и Без ограничения общности можно считать, что Тогда, поскольку образуют последовательных чисел, среди них должно быть и число (поскольку Но это число делится на (так как четно), что невозможно. Противоречие.

Заметим, что в разложение трёхзначного числа на простые множители входит не более двух множителей, больших — иначе произведение будет больше Кроме того, среди последовательных натуральных чисел есть число, делящееся на в разложение которого входит максимум один множитель, больший

Таким образом, в разложения десяти последовательных трёхзначных чисел входит не более простых множителей, больших Вместе с множителями получается не больше различных простых множителей, что и требовалось доказать.