Задача
Для каждого натурального числа n обозначим через O(n) его наибольший нечётный делитель. Даны произвольные натуральные числа
х1 = а и х2 = b. Построим бесконечную последовательность натуральных чисел по правилу: xn = O(хn–1 + хn–2), где n = 3, 4, ... .
а) Докажите, что, начиная с некоторого места, все числа в последовательности будут равны одному и тому же числу.
б) Как найти это число, зная числа a и b?
Решение
а) xn нечётно при n > 2, поэтому xn+2 ≤ ½ (хn+1 + хn). Следовательно, последовательность yn = max {xn+1, xn} не возрастает. Поскольку бесконечное убывание невозможно, эта последовательность стабилизируется: ym = ym+1 = ym+2 = ... Если xm ≠ xm+1 ≠ xm+2, то xm+2 < ym, xm+3 < ym+1 = ym и
ym+2 < ym – противоречие. Значит, xm+1 = xm+2 = xm+3 = ... б) Пусть xm = xm+1 = xm+2 = ... Обозначим δ = O(НОД(a, b)). Ясно, что все хn (в частности, xm) кратны δ. С другой стороны, xm–1 = 2kxm+1 – xm кратно xm, значит, xm–2 кратно xm. Продолжая, получим, что a и b кратны xm. Следовательно, δ кратно xm, то есть δ = xm.
Ответ
б) Это O(НОД(a, b)).
Чтобы оставлять комментарии, войдите или зарегистрируйтесь