Consider the sequence: $x_1=19,x_2=95,x_{n+2}=\text{lcm} (x_{n+1},x_n)+x_n$, for $n>1$, where $\text{lcm} (a,b)$ means the least common multiple of $a$ and $b$. Find the greatest common divisor of $x_{1995}$ and $x_{1996}$.
Problem
Source: 0
Tags: number theory, greatest common divisor, least common multiple
MellowMelon
25.08.2007 21:53
(using $ (a,b)$ for GCD and $ [a,b]$ for LCM)
If $ a$ and $ b$ are two natural numbers and $ c$ = $ [a,b]+a$, then clearly $ (a,b) = (b,c)$ by the Euclidean algorithm. By this fact, the GCD of any two adjacent terms in the sequence is equal to $ (x_{1},x_{2})$, which is $ 19$.
nayel
25.08.2007 22:04
$ x_{n+1}=[x_{n}, x_{n-1}]+x_{n-1}$. So $ x_{n+2}=[x_{n+1}, x_{n}]+x_{n}=[[x_{n}, x_{n-1}],x_{n}]+x_{n}=[x_{n}, x_{n-1}]+x_{n-1}$. which implies $ x_{n}=[x_{1},x_{2}]+x_{n-1}=95+x_{n-1}$
MellowMelon
25.08.2007 22:13
Something's wrong in that hint. $ x_{3}= 114$ and $ x_{4}= 665$. I think when you substituted the $ x_{n+1}$ in the LCM, you forgot to add $ x_{n-1}$ inside of it. That changes a lot.