Team selection tests

The general formula for the sequence is $x_n={\alpha }^n+{\beta }^n$ with $\alpha$ and $\beta$ such that $$\alpha +\beta =a,\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{array}{rl}{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{array}$$ is divisible by $x_m$. So we have $$x_m\mid x_n\iff x_m\mid b^m{x}_{n-2m}\iff 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{array}{rl}{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{array}$$ 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{array}{rl}\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}+\cdots +b^{(k-1)n}{x}_{2n}+b^{kn}\end{array}$$ 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{array}{rl}{x}_{2k}& ={\alpha }^{2k}+{\beta }^{2k}\\ & =({\alpha }^k-{\beta }^k{)}^2+2b^{2k}.\end{array}$$ On the other hand, $$\begin{array}{rl}({\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{array}$$ 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(\mathrm{mod}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$