42nd Balkan Mathematical Olympiad

Solution 1. Let $n\ge 2025$ and $y_n=\frac{n^2+a}{x_n}$. Also let $z_n=\frac{n^2+b}{x_n+k}$. Consider $c_n=y_n-z_n$. We have $$|c_n|=\left|\frac{n^2}{x_n}-\frac{n^2}{x_n+k}+\frac{a}{x_n}-\frac{b}{x_n+k}\right|=\left|k\cdot \frac{n^2}{x_n(x_n+k)}+\frac{a}{x_n}-\frac{b}{x_n+k}\right|<k+\frac{a+b}{n}$$ so $c$ can take finitely many values. Furthermore, $(x_n+k)(y_n-c_n)=n^2+b$ expands into $k{y}_n=u_n+c_n{x}_n$, where $u_n=b+k{c}_n-a$ only depends on $c_n$. From these we can easily get $$4c_{n}k{n}^2=(2c_{n}x+u_n{)}^2-(u_n^2+4a{c}_{n}k).(1)$$ As $c_n$ is bounded, expressions $4c_{n}k$ and $u_n^2+4a{c}_{n}k$ each take finitely many values as $n$ varies through positive integers. Lemma. For any pair of integers $(a,b)$ such that either $a$ is not a perfect square or $b\ne 0$ there exist infinitely many primes $p$ together with a residue class $n$ such that $a{n}^2+b$ is a quadratic non-residue mod $p$. Proof. Let $p$ be a large prime with $p\nmid a,b$. Assume that the claim is not true and let $n=1,2,\dots ,\frac{p-1}{2}$. Since expressions $a{n}^2+b$ produce different residues, we get equality on the sets of residues: $$\{1^2,2^2,\dots ,{\left(\frac{p-1}{2}\right)}^2\}=\{a\cdot 1^2+b,a\cdot 2^2+b,\dots ,a\cdot {\left(\frac{p-1}{2}\right)}^2+b\}.$$ Summing both sets yields $aS+\frac{p-1}{2}b\equiv S(\mathrm{mod}p)$ where $S=1^2+2^2+\cdots +{\left(\frac{p-1}{2}\right)}^2=\frac{p(p-1)(p+1)}{24}\equiv 0(\mathrm{mod}p)$, since $p$ is a large prime. Therefore $p\mid b$, which is a contradiction. Since we can pick infinitely many integers from a class mod $p$, the lemma follows. □ Let $(a_i,b_i)$ for $i\in \{1,2,\dots ,l\}$ be all the possible values of $(4c_{n}k,u_n^2+4a{c}_{n}k)$. Claim. Let $a_i{n}^2+b_i=m^2$ be a finite collection of conics such that for each one either $a_i$ is not a perfect square or $b_i\ne 0$. Then, there exist infinitely many positive integers $n$ such that none of $n,n+1,n+2$ belong to any of these conics. Proof. Let $p_{i,0},p_{i,1},p_{i,2}$ and $n_{i,0},n_{i,1},n_{i,2}$ be three primes and their corresponding residues that the lemma provides for the pair $(a_i,b_i)$. Note that since lemma provides infinitely many primes for each pair $(a_i,b_i)$, we can ensure that all mentioned primes are distinct. By choosing $n$ to satisfy $$\begin{array}{rl}n& \equiv n_{i,0}(\mathrm{mod}{p}_{i,0}),\\ n+1& \equiv n_{i,1}(\mathrm{mod}{p}_{i,1}),\\ n+2& \equiv n_{i,2}(\mathrm{mod}{p}_{i,2}),\end{array}$$ for all $i$, we see that none of $a_i{n}^2+b_i$, $a_i(n+1{)}^2+b_i$, $a_i(n+2{)}^2+b_i$ can be a perfect square for any $i$ (since each expression is a quadratic non-residue modulo some prime). Since there are obviously infinitely many such $n$, the claim follows. □ ---

To finish the solution, pick a large enough positive integer $n$ from the claim. If $c_n\ne 0$ we get that $4c_{n}k$ is a square and $u_n^2+4a{c}_{n}k=0$. Therefore $u_n^2+4a{c}_{n}k=u_n^2+a{t}^2=0$ for some integer $t$. Since $a$ is a positive integer it follows that $t=0$ and thus $c_n=0$. Then $y_n=z_n$, so $k{y}_n=b-a$. Furthermore, as this also holds for $n+1$ and $n+2$, we get that $y_n=\frac{b-a}{k}$ divides $$n^2+a,(n+1{)}^2+a,(n+2{)}^2+a.$$ By simple calculations we obtain $y_n=1$. Therefore $k=b-a$.

Solution 2. We can find values of $n$ that do not belong to any of the conics from the lemma in a different way. We will first find one value of $n$ which does not belong to any of those conics. Let $p_1,p_2,\dots ,p_k$ be all the primes less than or equal to $\max \{|b_i|\}$ and let ${\alpha }_i=v_{p_i}((\max \{|b_i|\})!)$. Then, let $p\equiv 3(\mathrm{mod}4)$ be a large enough prime number (such that it is not equal to any $p_i$). Claim. Number $n_0=p{\prod }_{1\le i\le k}{p}_i^{{\alpha }_i}$ does not belong to any of the conics. Proof. Assume otherwise and let $b_i+a_i{n}_0^2=m^2$. For all primes $q\mid b_i$ it holds that $v_q(b_i)<v_q(a_i{n}_0^2)$, implying $v_q(b_i)=v_q(m^2)$. Therefore $|b_i|$ is a square and we can divide the whole equation with $|b_i|$. We are left with $$\pm 1+a_i(n_0^{\prime }{)}^2=(m^{\prime }{)}^2.$$ Since $p\equiv 3(\mathrm{mod}4)$, the case $-1$ is impossible, thus $b_i$ is positive. Subtracting 1 from both sides yields $$a_i(n_0^{\prime }{)}^2=(m^{\prime }-1)(m^{\prime }+1),$$ which is impossible as $p^2$ divides precisely one factor on the right, but by choice of $p$ it holds that $(m^{\prime }-1)(m^{\prime }+1)\ge (p^2-1)(p^2+1)=p^4-1\gg a_i(n_0^{\prime }{)}^2$ (and $p>a_i$). $\square$ Similarly as in solution 1 we get that $c_n=0$ and $\frac{b-a}{k}=y_n$ is a positive integer. Assume there exists a prime $q\mid \frac{b-a}{k}$. Claim. There exist two positive integers $n_1,n_2$, both of which do not belong to any of the conics from solution 1, such that $q\mid n_1$ and $q\nmid n_2$. Proof. If $q\nmid n_0$, let $p_0\equiv 3(\mathrm{mod}4)$ be a prime such that $p_0>p$ and $p_0^4\gg a_i(q{n}_0^{\prime }{)}^2$. Then, similarly as $n_0$, the number $n_1=q{p}_0\frac{n_0}{p}$ is shown to not belong to any of the conics. Therefore $n_1$ and $n_0$ are the desired positive integers. Assume $q\mid n_0$ and $q>2$. Let $s$ be a quadratic non-residue mod $q$. By Dirichlet's theorem there exists a prime $r\gg p$ such that $$r\equiv 1(\mathrm{mod}4)$$ $$r\equiv s(\mathrm{mod}q).$$ Then $r$ is also a quadratic non-residue mod $q$ and then $(\frac{r}{q})(\frac{q}{r})=1$ by the law of quadratic reciprocity, which means $(\frac{q}{r})=(\frac{-q}{r})=\frac{-1}{1}=-1$. (1) Let $n_2=rp{\prod }_{1\le i\le k,p_i\ne q}{p}_i^{{\alpha }_i}$. Assume $a_i{n}_2^2+b_i=m^2$ for some integer $m$. Similarly as in the previous claim, after reducing the equation with $\gcd (a_i{n}_2^2,b_i,m^2)$ we are left with $$\pm q^{2h}+a_i(n_0^{\prime }{)}^2=(m^{\prime }{)}^2\text{or}\pm q^{2h+1}+a_i(n_0^{\prime }{)}^2=(m^{\prime }{)}^2,$$

where $v_q(b_i)=2h$ or $v_q(b_i)=2h+1$ for some nonnegative integer $h$. Since $q^{2h}\le |b_i|$, the first form is impossible similarly as in the previous claim and the second form is impossible due to (1). If $q=2$ we define $r\gg p$ such that $r\equiv 5(\mathrm{mod}8)$, which yields $(\frac{2}{r})=(\frac{-2}{r})=-1$, and proceed analogously. Therefore $n_0$ and $n_2$ are the desired positive integers in this case. $\square$ To finish the proof, note that $q\mid \frac{b-a}{k}\mid n_1^2+a$, and thus $q\mid a$. We also have $q\mid \frac{b-a}{k}\mid n_2^2+a$, which is a contradiction since $q\nmid n_2$. Therefore no prime divides $\frac{b-a}{k}$, and since $\frac{b-a}{k}$ is a positive integer, we conclude $\frac{b-a}{k}=1$, that is $k=b-a$.