Задача 30604

Темы:    [ Деление с остатком ] [ Классическая комбинаторика (прочее) ] [ Перебор случаев ]

Сложность: 3- Классы: 7,8,9

Условие

Сколько существует натуральных чисел n, меньших 10000, для которых  2ⁿ – n²  делится на 7?

Решение

Остатки от деления 2ⁿ на 7 повторяются с периодом 3:  2, 4, 1. Остатки от деления n² на 7 повторяются с периодом 7:  1, 4, 2, 2, 4, 1, 0. Поэтому делимость на 7 зависит только от остатка при делении n на 21. Рассмотрим все случаи (в первой строке таблицы – остатки от деления на 21, в следующих двух – остатки от деления на 7).

Мы видим 6 случаев совпадений (когда n ≡ 2, 4, 5, 6, 10, 15 (mod 21)).  10000 = 476·21 + 4.  Поэтому количество "подходящих" чисел равно  476·6 + 2 = 2858.

Ответ

2858 чисел.

Источники и прецеденты использования

книга
Автор	Генкин С.А., Итенберг И.В., Фомин Д.В.
Год издания	1994
Название	Ленинградские математические кружки
Издательство	Киров: "АСА"
Издание	1
глава
Номер	10
Название	Делимость-2
Тема	Теория чисел. Делимость
задача
Номер	018