Рассмотрим периодичность остатков от деления на 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.
Answers & Comments
Verified answer
Рассмотрим периодичность остатков от деления на 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.