Задание олимпиады: делимость 2ⁿ – n² на 7 и подсчёт подходящих n

Остатки от деления 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.