Define a sequence: $x_0=1$ and for all $n\ge 0$, $x_{2n+1}=x_{n}$ and $x_{2n+2}=x_{n}+x_{n+1}$. Prove that for any relatively prime positive integers $a$ and $b$, there is a non-negative integer $n$ such that $a=x_n$ and $b=x_{n+1}$.
Source: 2021 Macedonian Balkan MO TST - Problem 2
Tags: number theory, Sequences
Define a sequence: $x_0=1$ and for all $n\ge 0$, $x_{2n+1}=x_{n}$ and $x_{2n+2}=x_{n}+x_{n+1}$. Prove that for any relatively prime positive integers $a$ and $b$, there is a non-negative integer $n$ such that $a=x_n$ and $b=x_{n+1}$.