Олимпиадная задача: последовательность натуральных чисел и делимость н
Последовательность a1, a2, a3, ... натуральных чисел такова, что an+2 = an+1an + 1 при всех n.
а) a1 = a2 = 1. Докажите, что ни один из членов последовательности не делится на 4.
б) Докажите, что an – 22 – составное число при любом n > 10.
Разобрать решение
а) Выпишем остатки от деления членов последовательности на 4: 1, 1, 2, 3, 3, 2, 3, ... Видно, что, начиная с третьего члена, они повторяются с периодом 3.
б) an+2 ≡ 1 (mod an+1), an+3 ≡ 1 (mod an+1), an+4 ≡ 1·1 + 1 = 2 (mod an+1), an+5 ≡ 2·1 + 1 = 3 (mod an+1), an+6 ≡ 3·2 + 1 = 7 (mod an+1),
an+7 ≡ 7·3 + 1 = 22 (mod an+1).
Кроме того, an ≥ 2 при n ≥ 3, поэтому an+7 – 22 ≥ 26an+1 – 22 > an+1 при n > 3.
Обсуждение
0Комментариев пока нет.
Чтобы оставить комментарий, войдите в аккаунт.