РЕШУ ОЛИМП, математика: задания, ответы, решения

Задания

Версия для печати и копирования в MS Word

Тип 0 № 1674 Добавить в вариант

Последовательности {x_n}, {y_n} заданы условиями $x_1=11,$ $y_1=7,$ $x_n плюс 1=3x_n плюс 2y_n,$ $y_n плюс 1=4x_n плюс 3y_n,$ $n принадлежит N .$ Найдите остаток от деления числа $y_1855 в степени левая круглая скобка 2018 правая круглая скобка минус 2x_1855 в степени левая круглая скобка 2018 правая круглая скобка$ на 2018.

Спрятать решение

Решение.

При всех $n принадлежит N$ числа $x_n$ и $y_n$ нечётны. Заметим, что

$2 x_n плюс 1 в квадрате минус y_n плюс 1 в квадрате =2 левая круглая скобка 3 x_n плюс 2 y_n правая круглая скобка в квадрате минус левая круглая скобка 4 x_n плюс 3 y_n правая круглая скобка в квадрате =2 x_n в квадрате минус y_n в квадрате .$

Следовательно,

$2 x_n в квадрате минус y_n в квадрате =\ldots=2 x_1 в квадрате минус y_1 в квадрате =242 минус 49=193 .$

Пусть $p=1009 .$ Это число нечётное и простое, поэтому число

$левая круглая скобка y_n в квадрате минус 2 x_n в квадрате правая круглая скобка в степени левая круглая скобка p правая круглая скобка = левая круглая скобка минус 193 правая круглая скобка в степени левая круглая скобка p правая круглая скобка$

даёт тот же остаток при делении на $2 p,$ что и $y_n в степени левая круглая скобка 2 p правая круглая скобка минус 2 в степени левая круглая скобка p правая круглая скобка x_n в степени левая круглая скобка 2 p правая круглая скобка ,$ так как все биномиальные коэффициенты $C_p, \ldots в степени левая круглая скобка 1 правая круглая скобка \ldots, C_p в степени левая круглая скобка p минус 1 правая круглая скобка$ делятся на p. Кроме того, по малой теореме Ферма, $2 в степени левая круглая скобка p правая круглая скобка$ при делении на $2 p=2018$ даёт остаток 2 (и, следовательно, остатки от деления чисел $y_n в степени левая круглая скобка 2 p правая круглая скобка минус 2 в степени левая круглая скобка p правая круглая скобка x_n в степени левая круглая скобка 2 p правая круглая скобка$ и $y_n в степени левая круглая скобка 2 p правая круглая скобка минус 2 x_n в степени левая круглая скобка 2 p правая круглая скобка$ одинаковы), a $левая круглая скобка минус 193 правая круглая скобка в степени левая круглая скобка p правая круглая скобка$ при делении на $2 p=2018$ даёт остаток $2018 минус 193=1825.$

Ответ: 1825.

Аналоги к заданию № 1674: 1675 Все

Олимпиада школьников Ломоносов, 10, 11 класс, 1 тур (отборочный) 1 этап, 2019 год

Классификатор: Анализ. Последовательности, Методы алгебры. Преобразования выражений

Спрятать решение · Помощь