For any positive integer $k$ denote by $S(k)$ the number of solutions $(x,y)\in \mathbb{Z}_+ \times \mathbb{Z}_+$ of the system $$\begin{cases} \left\lceil\frac{x\cdot d}{y}\right\rceil\cdot \frac{x}{d}=\left\lceil\left(\sqrt{y}+1\right)^2\right\rceil \\ \mid x-y\mid =k , \end{cases}$$where $d$ is the greatest common divisor of positive integers $x$ and $y.$ Determine $S(k)$ as a function of $k$. (Here $\lceil z\rceil$ denotes the smalles integer number which is bigger or equal than $z.$)
Problem
Source: Moldova TST 2019
Tags: number theory
Math1Zzang
11.03.2019 16:49
If $y=x+k$ then $\frac{x\cdot d}{y}<d$, so $\left\lceil\frac{x\cdot d}{y}\right\rceil\cdot \frac{x}{d}\leq x<y<\left\lceil\left(\sqrt{y}+1\right)^2\right\rceil$, contradiction.
Therefore $x=y+k$.
$y+2+2\sqrt{y}>\left\lceil\left(\sqrt{y}+1\right)^2\right\rceil=\left\lceil\frac{x\cdot d}{y}\right\rceil\cdot \frac{x}{d}\geq \frac{x^2}{y}=y+2k+\frac{k^2}{y}>y+2k$, so $y>(k-1)^2$
Now $\frac{x\cdot d}{y}=d+\frac{k\cdot d}{y}$, so $\left\lceil\frac{x\cdot d}{y}\right\rceil\cdot \frac{x}{d}=x+\left\lceil\frac{k\cdot d}{y}\right\rceil\cdot \frac{x}{d}$
Meanwhile, $\left\lceil\left(\sqrt{y}+1\right)^2\right\rceil=y+1+\lceil 2\sqrt{y}\rceil$, so the equation becomes \[k+\left\lceil\frac{k\cdot d}{y}\right\rceil\cdot \frac{x}{d}=1+\lceil 2\sqrt{y}\rceil\]Case 1. $d=k$
Then $d$ divides $y$. Let $y=ky'$. Since $y>(k-1)^2$, $y'\geq k-1$.
If $y'\geq k$, then $\left\lceil\frac{k\cdot d}{y}\right\rceil=1$, so $k+y'+1=1+\lceil 2\sqrt{ky'}\rceil$
We can easily check that $y'$ such that $k\leq y'<k+2\sqrt{k}+1$ is possible, so there are $\lceil 2\sqrt{k}+1\rceil$ solutions.
If $y'=k-1$, then $\left\lceil\frac{k\cdot d}{y}\right\rceil=2$, so the equation becomes $3k=2k$, which is a contradiction.
Case 2. $d<k$
Case 2-1. k=2,d=1
Then the equation becomes $2+\left\lceil\frac{2}{y}\right\rceil\cdot(y+2)=1+\lceil 2\sqrt{y}\rceil$.
We can easily see that there are no solutions.
Case 2-2. Otherwise...
Since $d$ is a divisor of $k$, $d\leq \frac{k}{2}$, so $d\leq k-2$.
Therefore $y>(k-1)^2>k(k-2)\geq kd$, so the equation becomes $k+\frac{k+y}{d}=1+\lceil 2\sqrt{y}\rceil$.
Since $y>k(k-2)$, $\frac{y}{d}\geq \frac{y}{k-2}\geq \frac{y}{k}+2$. Also, $\frac{k}{d}\geq 1$.
$\therefore k+\frac{k+y}{d}\geq 3+k+\frac{y}{k}\geq 3+2\sqrt{y}>1+\lceil 2\sqrt{y}\rceil$. A contradiction!
From all cases, we get $S(k)=\lceil 2\sqrt{k}+1\rceil$. $\blacksquare$