Maths Olympiad Prep

Library / /27 of 48

Number theory Difficulty 6.0 AIME, harder Prove it Baltic Way

Problem:

Consider the sequence
x1=19,x2=95,xn+2=lcm⁡(xn+1,xn)+xn, \begin{aligned} x_{1} & = 19, \\ x_{2} & = 95, \\ x_{n+2} & = \operatorname{lcm}\left(x_{n+1}, x_{n}\right) + x_{n}, \end{aligned}
for n>1n > 1, where lcm⁡(a,b)\operatorname{lcm}(a, b) means the least common multiple of aa and bb. Find the greatest common divisor of x1995x_{1995} and x1996x_{1996}.

Solution

Solution:

Let d=gcd⁡(xk,xk+1)d = \operatorname{gcd}\left(x_{k}, x_{k+1}\right). Then lcm⁡(xk,xk+1)=xkxk+1/d\operatorname{lcm}\left(x_{k}, x_{k+1}\right) = x_{k} x_{k+1} / d, and
gcd⁡(xk+1,xk+2)=gcd⁡(xk+1,xkxk+1d+xk)=gcd⁡(xk+1,xkd(xk+1+d)). \operatorname{gcd}\left(x_{k+1}, x_{k+2}\right) = \operatorname{gcd}\left(x_{k+1}, \frac{x_{k} x_{k+1}}{d} + x_{k}\right) = \operatorname{gcd}\left(x_{k+1}, \frac{x_{k}}{d}\left(x_{k+1} + d\right)\right).
Since xk+1x_{k+1} and xk/dx_{k} / d are relatively prime, this equals gcd⁡(xk+1,xk+1+d)=d\operatorname{gcd}\left(x_{k+1}, x_{k+1} + d\right) = d. It follows by induction that gcd⁡(xn,xn+1)=gcd⁡(x1,x2)=19\operatorname{gcd}\left(x_{n}, x_{n+1}\right) = \operatorname{gcd}\left(x_{1}, x_{2}\right) = 19 for all n≥1n \geq 1. Hence gcd⁡(x1995,x1996)=19\operatorname{gcd}\left(x_{1995}, x_{1996}\right) = 19.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.