Олимпиадная задача по теории чисел для 9-10 классов от Агаханова Н. Х.
Задача
Пусть a1, ..., a11 – различные натуральные числа, не меньшие 2, сумма которых равна 407.
Может ли сумма остатков от деления некоторого натурального числа n на 22 числа a1, ..., a11, 4a1, 4a2, ..., 4a11 равняться 2012?
Решение
Предположим, что такое число n существует. Максимальный возможный остаток от деления на натуральное число m равен m – 1. Поэтому сумма остатков от деления произвольного числа на числа a1, ..., a11 не больше чем 407 – 11 = 396, а сумма остатков от деления его на числа 4a1, 4a2, ..., 4a11 не больше, чем 4·407 – 11 = 1617. Если бы все остатки были максимальными возможными, то их сумма равнялась бы 396 + 1617 = 2013. Поскольку эта сумма для нашего числа n равна 2012, то все остатки, кроме одного, – максимальные возможные, а один – на единицу меньше максимального возможного.
Значит, при некотором k один из остатков от деления n на числа ak и 4ak – максимальный возможный, а другой – на единицу меньше максимального возможного. Тогда одно из чисел n + 1 и n + 2 делится на ak, а другое – на 4ak, то есть два взаимно простых числа n + 1 и n + 2 делятся на ak ≥ 2. Это невозможно.
Ответ
Не может.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь