VMO

a. We can easily prove that $x_n={\alpha }^n+{\beta }^n$ for all positive integers $n$ where $\alpha <0<\beta$ are two roots of the equation ${\lambda }^2-\lambda -1=0$.

Suppose that $x_n$ is a prime number where $n$ is a positive integer with odd prime divisors. Then, $n$ has the form $pq$ where $p$ is an odd prime and $q$ is a natural number greater than 1. We have $$\begin{array}{rl}{x}_{pq}& ={\alpha }^{pq}+{\beta }^{pq}\\ & =({\alpha }^q+{\beta }^q)\left({\alpha }^{q(p-1)}-{\alpha }^{q(p-2)}{\beta }^q+\cdots -{\alpha }^q{\beta }^{q(p-2)}+{\beta }^{q(p-1)}\right)\\ & =x_q\left(x_{q(p-1)}+\cdots +(-1{)}^{\frac{(q+1)(p-1)}{2}}{x}_{2q}+(-1{)}^{\frac{(q+1)(p-1)}{2}}\right),\end{array}$$ so $x_q\mid x_{pq}$. On the other hand, the sequence $(x_n)$ is strictly increasing so $x_q>x_1=1$. Hence, $x_{pq}$ is a composite, which is a contradiction. Hence, if $x_n$ is a prime number then $n$ is a prime number or $n$ has no odd prime divisor.

b. Consider the following cases

• Case 1: $m=0$. By considering the remainder of $x_n$ modulo 2, it is easy to check that $x_n$ are even for all $3\mid n$ and odd in the remaining cases. Hence, all pairs $(m,n)$ satisfying in this case are $(0,3k)$ where $k$ is a positive integer.

• Case 2: $m=1$. Clearly, all pairs $(m,n)=(1,k)$ where $k$ is a positive integer are satisfied.

• Case 3: $m>1$. For every $k\ge l\ge 0$, we have $$({\alpha }^k+{\beta }^k)({\alpha }^l+{\beta }^l)-({\alpha }^{k+l}+{\beta }^{k+l})=(\alpha \beta {)}^l({\alpha }^{k-l}+{\beta }^{k-l})=(-1{)}^l({\alpha }^{k-l}+{\beta }^{k-l}).$$ Hence, $$x_{k+l}=x_k{x}_l-(-1{)}^l{x}_{k-l}.(1)$$ In other words, for every $k\ge 2l\ge 0$, we have $$x_k=x_{k-l}{x}_l-(-1{)}^l{x}_{k-2l}.$$ Hence, $x_k$ is divisible by $x_l$ if and only if $x_{k-2l}$ is divisible by $x_l$, $x_{k-2l}$ is divisible by $x_l$ if and only if $x_{k-4l}$ is divisible by $x_l$ (if $k\ge 4l$), ... In general, we have $x_k$ is divisible by $x_l$ if and only if $x_{k-2tl}$ is divisible by $x_l$ (if $k\ge 2tl,t\in \mathbb{N}$). (2)

Now, since $x_n$ is divisible by $x_m$ and $x_n\ge x_m\ge 3$ then $n\ge m>1$. Set $n=qm+r$ with $q\in {\mathbb{N}}^{\ast }$, $r\in \mathbb{N}$, $0\le r\le m-1$. Consider the following cases:

Case 3.1: $q$ is even. According to (2), we have $x_m\mid x_n$ if and only if $x_m\mid x_r$, implies that $x_r\ge x_m$. If $r\ge 1$, then from the above inequality, we obtain $r\ge m$ (because $(x_n)$ is strictly increasing), which is a contradiction. Hence $r=0$, however this sub-case also leads to a contradiction since $x_m\ge x_2=3>x_0=x_r$.

Case 3.2: $q$ is odd. According to (2), we have $x_m\mid x_n$ if and only if $x_m\mid x_{m+r}$. On the other hand, $x_{m+r}=x_m{x}_r-(-1{)}^r{x}_{m-r}$ so $x_m\mid x_n$ if and only if $x_m\mid x_{m-r}$. If $0<r<m$, we have $1\le m-r\le x_{m-r}<x_m$, which is a contradiction. Thus, $r=0$ and all satisfying pairs $(m,n)$ in this sub-case are $(m,(2k+1)m)$ where $k$ is a positive integer.

Therefore, all satisfying pairs are $(0,3k)$, $(1,k)$ and $(m,(2k+1)m)$ where $m,k$ are positive integers and $m>1$.