Сколько существует натуральных чисел n. не больших 10000, для которых 2^n - n^2 делится на 7

Рассмотрим периодичность остатков от деления на 7 двух выражений: 2^n и n^2.

Для 2^n:

При n=1: 2^1≡2 (mod 7)

При n=2: 2^2≡4 (mod 7)

При n=3: 2^3≡8≡1 (mod 7)

При n=4: (2^3) * 2≡1*2≡2 (mod 7) - начался новый период

Таким образом, длина периода равна 3.

Для n^2:

При n=1: 1^2≡1 (mod 7)

При n=2: 2^2≡4 (mod 7)

При n=3: 3^2≡9≡2 (mod 7)

При n=4: 4^2≡16≡2 (mod 7)

При n=5: 5^2≡25≡4 (mod 7)

При n=6: 6^2≡36≡1 (mod 7)

При n=7: 7^2≡0^2≡0 (mod 7)

Если представить число n как 7k+a, где a - некоторое неотрицательное целое число из промежутка [0; 6], то (7k+a) ^2≡49k^2+14ak+a^2≡a^2 (mod 7). Это значит, что число (7k+a) ^2 имеет такой же остаток от деления на 7, что и число a^2. Таким образом, при n=8 остаток от деления на 7 будет таким же, каков и остаток от деления на 7 числа 1. Для n=9 остаток такой же, как при n=2. Это значит, что длина периода остатков n^2 на 7 равна 7. Определим общую длину периода остатков от деления на 7 чисел 2^n и n^2. Это и будет как раз длиной периода остатков разности 2^n-n^2. НОК (3,7) = 21.

Это означает, что остаток от деления на 7 числа 2^1-1^2 совпадает с остатком от деления на 7 числа 2^22-22^2. И т. д.

Зачем это все было расписано? Число 2^n-n^2 делится нацело на 7, если остаток от деления на 7 этого выражения равен 0. Суть в том, чтобы посчитать количество нулевых остатков внутри одного периода, длина которого 21, затем умножить это на количество периодов, а затем добавить число нулевых остатков у оставшегося неполного периода, чтобы добрать до 10000.

Итак, количество периодов равно [10000/21]=476.

10000-476*21=4 - число остатков, которые надо будет добрать.

Рассмотрим полностью весь период остатков. В первой колонке выпишем номера n, во второй колонке - остатки от деления на 7 выражения 2^n, в третьей колонке - остатки от деления на 7 числа n^2.

n ... 2^n ... n^2

1 ... 2 ... 1

2 ... 4 ... 4

3 ... 1 ... 2

4 ... 2 ... 2

5 ... 4 ... 4

6 ... 1 ... 1

7 ... 2 ... 0

8 ... 4 ... 1

9 ... 1 ... 4

10 ... 2 ... 2

11 ... 4 ... 2

12 ... 1 ... 4

13 ... 2 ... 1

14 ... 4 ... 0

15 ... 1 ... 1

16 ... 2 ... 4

17 ... 4 ... 2

18 ... 1 ... 2

19 ... 2 ... 4

20 ... 4 ... 1

21 ... 1 ... 0

Среди этих остатков равными являются те, которые соответствуют таким n:

2,4,5,6,10,15.

Таким образом, среди первых 9996 n количество чисел вида 2^n-n^2, делящихся нацело на 7, равно 476*6=2856.

n=9997,9998,9999,10000 соответствуют n=1,2,3,4. Среди них равные остатки получаются при n=2,4. То есть к итоговому результату надо прибавить 2. В итоге получим 2856+2=2858.

Ответ: 2858.