Теория чисел на Иннополисе
Ошибка.
Попробуйте повторить позже
Бесконечная последовательность 
строится следующим образом: 
и для 
Докажите, что для любого целого 
найдется член этой последовательности, кратный 
Источники:
Подсказка 1
Так как нас интересует остаток при делении на d, логично попробовать рассмотреть последовательность b₁, b₂, b₃, ..., где b_i — остаток от а_i при делении на d. Что мы знаем об этой последовательности?
Подсказка 2
Мы хотим доказать, что в данной последовательности встретится 0. Мы знаем, что остатки могут принимать только конечное число значений, как это может помочь нам в доказательстве?
Подсказка 3
Так как члены исходной последовательности заданы рекуррентно, мы можем рассмотреть тройки последовательных членов нашей последовательности остатков, сколько всего есть таких троек? А сколько из них может быть различными?
Подсказка 4
Всего таких троек бесконечное число, ведь последовательность имеет бесконечное число членов! Но так как остатки при делении на d ограничены, то и различных троек у нас может быть лишь конечное число. О чем нам это говорит?
Подсказка 5
Тройки чисел будут повторяться! Более того, последовательность будет периодической (ведь по тройке чисел мы можем однозначно восстановить следующую тройку). Дополним нашу последовательность членом b₀ — остатком от а₀ = а₃ - а₁а₂ при делении на d, и учтем, что в силу периодичности последовательности этот остаток встретится вновь.
Зафиксируем произвольное целое 
и рассмотрим последовательность 
где 
— остаток при делении члена 
исходной последовательности на 
для всякого 
Требуется доказать, что в последовательности 
встретится
0.
Заметим, что количество троек 
бесконечно, при этом по каждой такой тройке можно однозначно определить как
предыдущую 
так и следующую тройку в последовательности, при этои количество различных троек конечно 
их не более
чем 
т.е. найдутся различные 
для которых
Из вышесказанного следует, что последовательность 
является периодической. Дополняя её элементом 
т.к.
делаем вывод, что 
(для найденных ранее различных 
откуда 
кратно 
что и требовалось доказать.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
