Vietnamese Mathematical Olympiad

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{aligned} x_{pq} &= \alpha^{pq} + \beta^{pq} \\ &= (\alpha^q + \beta^q) \left( \alpha^{q(p-1)} - \alpha^{q(p-2)} \beta^q + \dots - \alpha^q \beta^{q(p-2)} + \beta^{q(p-1)} \right) \\ &= x_q \left( x_{q(p-1)} + \dots + (-1)^{\frac{(q+1)(p-1)}{2}} x_{2q} + (-1)^{\frac{(q+1)(p-1)}{2}} \right), \end{aligned}$$
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}. \quad (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}^*$, $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$.