Question

Дана послідовність 1,1,2,3,7,22,..., кожен член якої дорівнює добутку попередніх двох плюс 1. Доведіть, що жоден член послідовності не ділиться на 4.

Answer 1

Остаток от произведения и суммы чисел всегда можно посчитать, взяв остатки исходных чисел, перемножив их или сложив, и затем от полученного произведения или суммы опять взяв остаток. Здесь получается последовательность остатков от деления на 4:
1,1, 2, 3, 3, 2, 3. Мы получили пару соседних остатков (2, 3), которая уже была раньше. Т.к. каждый следующий элемент однозначно определяется двумя предыдущими, то дальше последовательность остатков будет повторяться, т.е. будет 1,1,(2,3,3),(2,3,3),(2,3,3).., В этой периодической последовательности остатков нет 0, т.к. период состоит только из 2 и 3, значит ни один элемент не делится на 4.