МОШ 2022, 11 класс, задача 5
Таня последовательно выписывала числа вида для натуральных чисел и заметила, что при полученное число делится на . А при каком наименьшем она получит число, делящееся на ?
(Т. А. Гарманова)
Ответ
Решение. Пусть натуральное число таково, что делится на . Тогда делится на и на , поэтому — нечётное число, имеющее остаток при делении на . Помимо того, делится на . Заметим, что если два числа сравнимы по модулю (т. е. дают одинаковые остатки при делении на ), то седьмые степени этих чисел также сравнимы по модулю . Это означает, для нахождения искомого числа достаточно рассмотреть все целые числа из промежутка , удовлетворяющие сравнению .
Докажем теперь, что всякое сравнение вида имеет не более решений на отрезке , где — многочлен степени с целыми коэффициентами. Доказательство проведём индукцией по . При получаем сравнение вида , которое имеет не более одного решения, так как любое целое взаимно просто с . Пусть утверждение верно для всех многочленов степени . Рассмотрим многочлен . Если он не имеет корней, то утверждение выполнено. Если же у него есть корень, то многочлен можно представить в виде , а по предположению индукции многочлен имеет не более корней. Утверждение доказано.
Найдём теперь все решения сравнения на отрезке . Нам известны два решения: , . Заметим, что если — решение сравнения , то для любого натурального числа также являются решениями. Следовательно, решениями данного сравнения являются числа
Итак, мы нашли семь решений на отрезке : , , , , , , . По доказанному выше других решений на этом отрезке нет. Из них нечётными и имеющими остаток при делении на являются , , и . Из них наименьшее, большее , есть .
Ответ. .