Belarus2022

a) Let us prove the following Lemma. If for each integer $x$ the value of the polynomial $Q(x)=b{x}^2+cx+d$ with integer coefficients is a square of an integer, then there exist integers $m$ and $n$ such that $b=m^2$, $c=2mn$, $d=n^2$ and, in particular, $Q(x)=(mx+n{)}^2$.

Proof of the lemma. If $b=0$, then for each integer $x$ the difference $Q(x+1)-Q(x)=c$ is constant. Whereas the differences between neighboring squares of integers infinitely grow, so if $c\ne 0$ then the non-constant polynomial $Q(x)$ takes the same values infinitely many times, which is impossible. If $b=c=0$ then $d$ is a perfect square and the numbers $m=0$ and $n=\sqrt{d}$ fit in.

Let $b\ne 0$, then, obviously, $b>0$, since otherwise $Q(x)$ will be negative for sufficiently large $x$. If the discriminant $c^2-4bd$ is zero, then $Q(x)=b(x+\frac{c}{2b}{)}^2$. Since $4b^{2}Q(x)=b(2bx+c{)}^2$ is a perfect square for every integer $x$, $b$ is a perfect square. Let $b=e^2$, then $Q(x)=(ex+\frac{c}{2e}{)}^2$ is a perfect square for every integer value of $x$, which implies that $c$ is a multiple of $2e$ and $Q$ satisfies the lemma statement.

If the discriminant $c^2-4bd$ is not equal to zero, then among the prime divisors of the values $Q(x)$ in integer points choose a prime divisor $p$, greater than $|c^2-4bd|$. Let $Q(x)$ be a multiple of $p$. Consider $Q(x+p)$: $$Q(x+p)=Q(x)+b{p}^2+p(2bx+c).(1)$$ Note that $(2bx+c{)}^2=4aQ(x)+c^2-4bd$ is not a multiple of $p$, so $2bx+c$ is not a multiple of $p$ and from (1) we obtain $$v_p(Q(x+p))=v_p(Q(x))+1,$$ which is impossible because $Q(x)$ and $Q(x+p)$ are perfect squares. Therefore, this case is impossible and the lemma is proved.

Let's move on to solving the problem itself. Denote the polynomial given in the condition by $P(x,y)$. We will show that it can be decomposed into a product of two polynomials of the first degree with rational coefficients. Let $$P(x,y)=a_0{x}^2+a_1{y}^2+a_{2}xy+a_{3}x+a_{4}y+a_5.$$ Suppose $a_1\ne 0$. Consider $P(x,y)$ as a square trinomial of the variable $y$: $$P(y)=a_1{y}^2+(a_{2}x+a_4)y+(a_0{x}^2+a_{3}x+a_5).$$ Since this square trinomial has an integer root for any integer value $x$, its discriminant $$D(x)=(a_{2}x+a_4{)}^2-4a_1(a_0{x}^2+a_{3}x+a_5)$$ is a perfect square for all integer values of $x$. The degree of this polynomial is at most two, so we can apply the lemma to it. Hence $D(x)=(mx+n{)}^2$ for some integers $m$ and $n$. Then the polynomial $P(y)$ can be expanded into a product of two linear factors with rational coefficients $P(y)=a_1(y-y_1)(y-y_2)$, which can be written as $$P(x,y)=\frac{1}{4a_1}(2a_{1}y-(a_{2}x+a_4)-(mx+n))(2a_{1}y-(a_{2}x+a_4)+(mx+n)).$$ A similar expansion can be written in the case $a_0\ne 0$.

Suppose now that $a_0=a_1=0$. Since this polynomial has degree 2, $a_2\ne 0$ and $$P(x,y)=a_{2}xy+a_{3}x+a_{4}y+a_5.$$ By the problem statement, for any integer value $x$ the number $y=\frac{a_{3}x+a_5}{a_{2}x+a_4}$ is an integer, because $P(x,y)=0$ can be true only for it. Hence, for any integer value $x$ the number $$a_2(a_{3}x+a_5)-a_3(a_{2}x+a_4)=a_2{a}_5-a_3{a}_4$$ is a multiple of the denominator $a_{2}x+a_4$, which is possible only if $a_2{a}_5=a_3{a}_4$. The number $t=\frac{a_3}{a_2}$ satisfies the equality $\frac{a_5}{a_4}=\frac{a_3}{a_2}=t$ (if $a_4=0$ then $a_5=0$, and the case $a_3=0$ is obviously impossible). Then $\frac{a_{3}x+a_5}{a_{2}x+a_4}=t$ for all integers $x$, which contradicts the problem statement for $b=t$. Therefore this case is impossible.

Thus, the polynomial $P(x,y)$ decomposes into a product of two polynomials of the first degree with rational coefficients, we write this equality in the form $$M\cdot P(x,y)=(k_{1}x+l_{1}y+C_1)(k_{2}x+l_{2}y+C_2),$$ where all coefficients are integers. Note that the equations $k_{1}x+l_{1}y+C_1=0$ and $k_{2}x+l_{2}y+C_2=0$ are linear Diophantine equations and there are three alternatives for each of them: 1) the equation has no entire solutions; 2) the equation has the constant solution on some variable; 3) the general solution of the equation has the form $(x_0+lt,y_0-kt),t\in \mathbb{Z}$. Moreover, the second alternative is impossible according to the problem condition, and in the third possibility we can always assume that the coefficients in the pairs $(k_1,l_1)$ and $(k_2,l_2)$ are coprime.

If $|l_i|=1$, then all solutions of $P(a,y)=0$ belongs to the corresponding bracket, so the first possibility holds for the other bracket and, consequently, $|k_i|$ is also equal to one, which gives the required multiplier in the problem condition. The case $|k_i|=1$ is considered similarly.

Consider the remaining case: all coefficients $k_i$ and $l_i$ are at least two in absolute value. Note that in the series of positive integers, each $|l_1|$-th number from the first bracket is a solution to the equation $P(x,b)=0$, as well as each $|l_2|$-th from the second bracket. Hence $\frac{1}{|l_1|}+\frac{1}{|l_2|}=1$ and similarly $\frac{1}{|k_1|}+\frac{1}{|k_2|}=1$. Under our assumptions this is only possible for $|l_1|=|l_2|=|k_1|=|k_2|=2$, which contradicts the fact that the coefficients must be coprime.

b) Consider the polynomial $P(x,y)=(3x-2y)(3x-4y+1)(3x-4y-1)$. Each of its factors is a linear function, and the zeros of these factors are the pairs $(2k,3k)$, $(4k+1,3k+1)$ and $(4k-1,3k-1)$, $k\in \mathbb{Z}$. It is easy to see that this polynomial satisfies the condition.