Problem 1869

The general formula for the sequence is $x_n = \alpha^n + \beta^n$ with $\alpha$ and $\beta$ such that
$$\alpha + \beta = a, \quad \alpha\beta = -b.$$

We will now prove $\gcd(b, x_m) = 1$ for all $m$. Indeed, suppose there are $m$ and a prime $p$ such that $x_m$ and $b$ are divisible by $p$. Since $\gcd(a, b) = 1$, $\gcd(a, p) = 1$. Since
$$x_m - b x_{m-2} = a x_{m-1}$$
results in $a x_{m-1}$ being divisible by $p$ or $x_{m-1}$ being divisible by $p$. By induction, we obtain $a_{m-2}, \dots, a_1$ are divisible by $p$ or $a$ is divisible by $p$, contradiction. Thus $b$ is coprime to all terms of the sequence.

We find the condition for the pairs $(m, n)$ with $m > 0$ such that $x_m \mid x_n$. It is easy to check that $(x_n)$ is a strictly increasing sequence of positive integers. Therefore, the necessary condition is $m \le n$. Next, if $n > 2m$, we have the following equation
$$\begin{aligned} x_n + (-b)^m x_{n-2m} &= \alpha^n + \beta^n + \alpha^m \beta^m (\alpha^{n-2m} + \beta^{n-2m}) \\ &= (\alpha^m + \beta^m)(\alpha^{n-m} + \beta^{n-m}) \end{aligned}$$
is divisible by $x_m$. So we have
$$x_m \mid x_n \Leftrightarrow x_m \mid b^m x_{n-2m} \Leftrightarrow x_m \mid x_{n-2m}.$$
Therefore, by induction, if $k$ is the remainder of $n$ when divided by $2m$, then $x_m \mid x_n$ if and only if $x_m \mid x_k$. Here are two cases:

* If $m \ge k$, then $x_k \le x_m$. Hence $x_m \mid x_n$ if and only if $x_m = x_k$ or $m = k$.
* If $m < k < 2m$, write $k = m + d$ with $0 < d < k$. We have
$$\begin{aligned} x_d x_m - x_{m+d} &= (\alpha^d + \beta^d)(\alpha^m + \beta^m) - \alpha^{m+d} - \beta^{m+d} \\ &= \alpha^d \beta^d (\alpha^{m-d} + \beta^{m-d}) \\ &= (-b)^d x_{m-d}. \end{aligned}$$
Therefore, $x_k$ is divisible by $x_m$ if and only if $(-b)^d x_{m-d}$ is divisible by $x_m$, i.e. $x_{m-d}$ is divisible by $x_m$, which contradicts the fact that $(x_n)$ is strictly increasing.

In short, for $m > 0$, we have $x_m \mid x_n$ if and only if $n = (2k+1)m$ for some natural number $k$.

a.

Since $x_0 = 2$ and $x_1 = a$ are even, we can inductively prove that $x_n$ is even for all $n$. Considering the quotient of $x_{(2k+1)n}$ with $x_n$, we have
$$\begin{aligned} \frac{x_{(2k+1)n}}{x_n} &= \frac{\alpha^{(2k+1)n} + \beta^{(2k+1)n}}{\alpha^n + \beta^n} \\ &= \sum_{i=0}^{k} (-1)^i \alpha^{ni} \beta^{ni} (\alpha^{n(2k-2i)} + \beta^{n(2k-2i)}) \\ &= x_{2kn} + b^n x_{(2k-2)n} + \dots + b^{(k-1)n} x_{2n} + b^{kn} \end{aligned}$$
is odd, because $b^{kn}$ is odd. So if $x_m$ is divisible by $x_n$ then $\frac{x_m}{x_n}$ is odd, so this fraction is not divisible by $x_p$.

b.

Consider three numbers $m, n, p$ such that $x_m$ is divisible by $x_n x_p$. Then, there exist natural numbers $k, l$ such that
$$m = (2k + 1)n = (2l + 1)p.$$
Since the product $mnp$ is even, all of three numbers are even. Set $m = 2u$, $n = 2v$ and $p = 2t$. For each natural number $k$:
$$\begin{aligned} x_{2k} &= \alpha^{2k} + \beta^{2k} \\ &= (\alpha^k - \beta^k)^2 + 2b^{2k}. \end{aligned}$$
On the other hand,
$$\begin{aligned} (\alpha^k - \beta^k)^2 &= (a^2 - 4b) \left( \sum_{i=0}^{\lfloor k/2 \rfloor} \alpha^i \beta^i (\alpha^{k-2i} + \beta^{k-2i}) \right)^2 \\ &= (a^2 - 4b) \left( \sum_{i=0}^{\lfloor k/2 \rfloor} (-b)^i x_{k-2i} \right)^2 \\ &= (a^2 - 4b) F_k^2 \end{aligned}$$
where $F_k$ is the expression inside the brackets. So by assumption, if $x_m x_n x_p$ is a perfect square then
$$\prod_{k \in \{u, v, t\}} \left( (a^2 - 4b) F_k^2 + 2b^{2k} \right).$$
Therefore, for every prime divisor $p$ dividing $a^2 - 4b$ then
$$1 = \left( \frac{2b^{2u} 2b^{2v} 2b^{2t}}{p} \right) = \left( \frac{2}{p} \right)$$
leads to $2$ which is a quadratic residue modulo $p$. This implies that $p$ has the form $8h+1$ or $8h+7$, for every prime divisor $p$ of $a^2 - 4b$. Thus $a^2 - 4b$ divided by $8$ leaves a remainder of $1$ or $7$. On the other hand, $a$ and $b$ are odd so
$$a^2 - 4b \equiv 1 - 4 \equiv 5 \pmod{8},$$
this is a contradiction. So $x_m x_n x_p$ is not a perfect square and the same for $\frac{x_m}{x_n x_p}$.

$\square$