a) Determine all 4-tuples $(x_0,x_1,x_2,x_3)$ of pairwise distinct intergers such that each $x_k$ is coprime to $x_{k+1}$(indices reduces modulo 4) and the cyclic sum $\frac{x_0}{x_1}+\frac{x_1}{x_2}+\frac{x_2}{x_3}+\frac{x_3}{x_1}$ is an interger. b)Show that there are infinitely many 5-tuples $(x_0,x_1,x_2,x_3,x_4)$ of pairwise distinct intergers such that each $x_k$ is coprime to $x_{k+1}$(indices reduces modulo 5) and the cyclic sum $\frac{x_0}{x_1}+\frac{x_1}{x_2}+\frac{x_2}{x_3}+\frac{x_3}{x_4}+\frac{x_4}{x_0}$ is an interger.
Problem
Source: Romania 2017 IMO TST 3, problem 1
Tags: number theory, abstract algebra
26.03.2018 07:11
26.03.2018 10:26
For a), I think the problem should be $\frac{x_0}{x_1}+\frac{x_1}{x_2}+\frac{x_2}{x_3}+\frac{x_3}{\color{red}{x_0}} \in \mathbb{Z}$. In that case, just note the the expression is equal to $\frac{x_0^2x_2x_3+x_1^2x_3x_0+x_1x_2^2x_0+x_1x_2x_3^2}{x_1x_2x_3x_0}$. Keep in mind that $\gcd (x_0,x_1)=\gcd (x_1,x_2) =\gcd (x_2,x_3) =\gcd(x_3,x_0)=1$. Simple divisibility checking gives us $x_1\mid x_3,x_2\mid x_0,x_3\mid x_1,$ and $x_0\mid x_2$. Since the integers must be pairwise distinct, we get $x_3=-x_1$ and $x_2=-x_0$. Plugging back in the expression gives $2\Big( \frac{x_0}{x_1}-\frac{x_1}{x_0}\Big) \in \mathbb{Z}\implies x_0\mid 2,x_1\mid 2$. Hence, all possible solutions are $$(1,2,-1,-2),(1,-2,-1,2),(-1,2,1,-2),(-1,-2,1,2),(2,1-2,-1),(-2,1,2,-1),(2,-1,-2,1),(-2,-1,2,1).$$ For b), not hard to see that the necessary (but may not sufficient) condition is $x_0\mid x_2x_3,x_1\mid x_3x_4,x_2\mid x_0x_4 ,x_3\mid x_0x_1,$ and $x_4\mid x_1x_2$. Choosing $x_0=bc,x_1=d,x_2=ac,x_3=bd,$ and $x_4=a$ where $a,b,c,d$ are pairwise co-prime positive integers verify all those conditions. Plugging back in the initial expression gives $\frac{x_0}{x_1}+\frac{x_1}{x_2}+\frac{x_2}{x_3}+\frac{x_3}{x_4}+\frac{x_4}{x_0} =\frac{ab^2c^2+bd^2+a^2c^2+b^2cd^2+a^2d}{abcd}$. So, we also need $d\mid a+b^2$ and $c\mid a^2+bd$. So, let's choose $d=a+b^2$ and $c=a^2+b(a+b^2)=a^2+ab+b^3$. Again, plugging in the expression, we've $$ab^2c^2+bd^2+a^2c^2+b^2cd^2+a^2d =(a+b^2)(a^2+ab+b^3)(a^3+a^2b+ab^3+b^2+1)=(a^3+a^2b+ab^3+b^2+1)cd.$$Hence, now the sufficient and necessary condition is $a\mid b^2+1$ and $b\mid a^3+1$ (not hard to verify the pairwise co-primeness of $a,b,c,d$.) Starting from $a_1=2$ and $b_1=9$, define the sequence $a_n$ and $b_n$ where $n\in \mathbb{Z}^+$ by the following recurrence relations: $a_{2i}=\frac{b_{2i-1}^2+1}{a_{2i-1}}$ and $b_{2i}=b_{2i-1}$ for all $i\in \mathbb{Z}^+$, and $a_{2i+1}=a_{2i}$ and $b_{2i+1}=\frac{a_{2i}^3+1}{b_{2i}}$ for all $i\in \mathbb{Z}^+$. Not hard to inductively see that $(a,b)=(a_n,b_n)$ always satisfy the required condition, and also $a_n+b_n$ is strictly increasing. Hence, we've construct infinite distinct such $(a,b)$, done.