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

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

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

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

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

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

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

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

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

Задача 1#68090

Последовательность целых чисел $a n$ задается следующим образом:

2 an+1 =an − an+ 1,a1 =100.

Докажите, что любые два различных члена последовательности взаимно просты.

Источники: БИБН - 2021, 11.3 (см. www.unn.ru)

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

Подсказка 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,$ а правая не делится, так что приходим к противоречию, которое доказывает взаимную простоту любых двух различных членов.