Задача 30609

Темы:    [ Периодичность и непериодичность ] [ Деление с остатком ] [ Рекуррентные соотношения (прочее) ]

Сложность: 4- Классы: 8,9,10

Условие

Последовательность a₁, a₂, a₃, ... натуральных чисел такова, что  a_n+2 = a_n+1a_n + 1 при всех n.
  а)  a₁ = a₂ = 1.  Докажите, что ни один из членов последовательности не делится на 4.
  б) Докажите, что  a_n – 22  – составное число при любом n > 10.

Подсказка

а) Рассмотрите остатки членов последовательности по модулю 4 и докажите, что они повторяются по циклу.
б)  a_n – 22  делится на a_n–6.

Решение

  а) Выпишем остатки от деления членов последовательности на 4:  1, 1, 2, 3, 3, 2, 3, ...  Видно, что, начиная с третьего члена, они повторяются с периодом 3.
  б)  a_n+2 ≡ 1 (mod a_n+1),  a_n+3 ≡ 1 (mod a_n+1),  a_n+4 ≡ 1·1 + 1 = 2 (mod a_n+1),  a_n+5 ≡ 2·1 + 1 = 3 (mod a_n+1),  a_n+6 ≡ 3·2 + 1 = 7 (mod a_n+1),
a_n+7 ≡ 7·3 + 1 = 22 (mod a_n+1).
  Кроме того,  a_n ≥ 2  при  n ≥ 3,  поэтому  a_n+7 – 22 ≥ 2⁶a_n+1 – 22 > a_n+1  при  n > 3.

Источники и прецеденты использования

книга
Автор	Генкин С.А., Итенберг И.В., Фомин Д.В.
Год издания	1994
Название	Ленинградские математические кружки
Издательство	Киров: "АСА"
Издание	1
глава
Номер	10
Название	Делимость-2
Тема	Теория чисел. Делимость
задача
Номер	023