Последовательности и прогрессии на БИБНе —Каталог задач по Олимпиадной математике

Главная
Каталог задач
Каталог заданий по Олимпиады - Математика
Последовательности и прогрессии на БИБНе

Тема БИБН (Будущие исследователи - будущее науки)

Последовательности и прогрессии на БИБНе

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела бибн (будущие исследователи - будущее науки)

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#68090

Последовательность целых чисел $a n$ задается следующим образом: $a = a2 − a +1,a = 100 n+1 n n 1$ . Докажите, что любые два различных члена последовательности взаимно просты.

Подсказки к задаче

Подсказка 1

Пупупу, нужно доказать взаимную простоту двух чисел… Попробуйте для начала взять первый и второй члены последовательности и посмотреть, какие у них могут быть общие множители и как они отличаются.

Подсказка 2

Можно посмотреть остаток любого члена последовательности по модулю предыдущего... и тут он оказывается равным единице! А что это значит?

Подсказка 3

А это значит, что единица должна делиться на потенциальный общий множитель, ведь мы имеем равенство по типу a₂ = a₁ * k + 1. Но ведь 1 делится только на 1, так что числа взаимнопросты! Теперь как-то надо обобщить это на все члены последовательности...

Подсказка 4

Ага, можно же воспользоваться индукцией!

Показать доказательство

Пусть $a n$ и $a n+m$ — два произвольных члена последовательности $(n,m ∈ℕ)$ . Докажем по индукции, что

an+m − an ⋅Nnm =1,

где $Nnm ∈ ℕ,$ то есть что $an+m− 1$ делится нацело на $an$ , а в терминах сравнения по модулю: $an+m ≡ 1. an$

Из этого будет следовать, что если нашлись два различных не взаимно простых члена последовательности $ak$ и $ak+l$ $(k,l∈ℕ )$ , которые имеют общий множитель $d ∈ℕ,d> 1,$ то в равенстве

ak+l− ak⋅Nkl = 1

левая часть делится на $d >1,$ а правая не делится, так что приходим к противоречию, которое доказывает взаимную простоту любых двух различных членов.