Последовательности {Xn},{Yn} заданы условиями X1=13, Y1=9, Xn+1(n+1 член)=3Xn+2Yn, Yn+1 (n+1 член)=4Xn+3Yn, nϵN. найдите остаток от деления числа Y1711^2018 - 2X1711^2018 на 2018. (Разность 1711 члена Y в степени 2018 и 2 умножить на 1711 член X в степени 2018)

задан 9 Ноя 2:19

10|600 символов нужно символов осталось
1

Число 2018 равно 2p, где p=1009 простое. Согласно малой теореме Ферма, a^p-a делится на p при любом целом a. Отсюда следует, что a^{2p}-a^2 делится на p. Но эта разность делится также на 2, так как степени a имеют одну и ту же чётность. Следовательно, a^{2018}-a^2 всегда делится на 2p=2018, и при нахождении остатков можно заменить 2018-е степени на квадраты.

Теперь заметим, что выражение Y^2-2X^2 не меняется при преобразовании X=3x+2y, Y=4x+3y. Это проверяется непосредственно: (4x+3y)^2-2(3x+2y)^2=y^2-2x^2. Следовательно, y(n)^2-2x(n)^2 всегда одно и то же (индукция по n). Оно равно y(1)^2-2x(1)^2=81-338=-257.

Таким образом, в ответе получится остаток 2018-257=1761. (От номера 1711 он не зависит.)

ссылка

отвечен 9 Ноя 12:39

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×3,827

задан
9 Ноя 2:19

показан
274 раза

обновлен
9 Ноя 12:39

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru