Задача 78515

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

Сложность: 3+ Классы: 7,8,9

Условие

Последовательность a₀, a₁, a₂, ... образована по закону:  a₀ = a₁ = 1,  a_n+1 = a_na_n–1 + 1.  Доказать, что число a₁₉₆₄ не делится на 4.

Решение

Остаток произведения (суммы) зависит только от остатков сомножителей (слагаемых). Используя это, выпишем последовательность остатков при делении на четыре чисел a_i: 1, 1, 2, 3, 3, 2, 3, ... Дальше последовательность периодична с периодом 3. Следовательно, ни один член этой последовательности не делится на 4.

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

олимпиада
Название	Московская математическая олимпиада
год
Номер	27
Год	1964
вариант
	1
Класс	7
Тур	1
задача
Номер	5