Задача 76478

Темы:    [ Арифметика остатков (прочее) ] [ Периодичность и непериодичность ]

Сложность: 4+ Классы: 8,9,10

Условие

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

Решение

Остатки от деления на 7 чисел 2^x и x² повторяются с периодами 3 и 7, поэтому остатки от деления на 7 числа 2^x – x² повторяются с периодом 21. Среди чисел x от 1 до 21 равные остатки от деления на 7 чисел 2^x и x² дают ровно 6 чисел. Поэтому среди чисел от 1 до  9996 = 21·476  есть 476·6 = 2856  требуемых чисел. Непосредственная проверка с использованием полученной последовательности остатков показывает, что из оставшихся чисел 9997, 9998 и 9999 только число 9998 обладает требуемым свойством.

Ответ

2857.

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

олимпиада
Название	Московская математическая олимпиада
год
Номер	6
Год	1940
вариант
Класс	9,10
Тур	2
задача
Номер	5