MathDB
lcm/gcd sequence

Source: 2015 ISL N4

July 7, 2016
number theoryIMO Shortlistgreatest common divisor

Problem Statement

Suppose that a0,a1,⋯a_0, a_1, \cdots and b0,b1,⋯b_0, b_1, \cdots are two sequences of positive integers such that a0,b0≥2a_0, b_0 \ge 2 and an+1=gcd⁡(an,bn)+1,bn+1=lcm⁡(an,bn)−1. a_{n+1} = \gcd{(a_n, b_n)} + 1, \qquad b_{n+1} = \operatorname{lcm}{(a_n, b_n)} - 1. Show that the sequence ana_n is eventually periodic; in other words, there exist integers N≥0N \ge 0 and t>0t > 0 such that an+t=ana_{n+t} = a_n for all n≥Nn \ge N.
Back to ProblemsView on AoPS