Determine the positive integers expressible in the form $\frac{x^2+y}{xy+1}$, for at least $2$ pairs $(x,y)$ of positive integers
Problem
Source: Romania TST 2016 Day 5 Problem 1
Tags: number theory
02.06.2016 08:46
We will begin with an auxiliary result: All ordered pairs of positive integers $(x,y)$ satisfying $xy+1|x^2+y$ are one of the forms $(a^2,a),(1,a),(a-1,a)$, where $a\in\mathbb N$. Proof: Suppose $(x,y)$ is a solution. Then $\frac{x^2+y}{xy+1}$ is an integer, say $k$. We have $$xy+1|x^2+y\iff xy+1|x^2y^2+y^3=(x^2y^2-1)+(y^3+1)\iff xy+1|y^3+1.$$ Thus the problem reduces to finding divisors of $y^3+1$ which are $1\pmod{y}$. Two trivial factors are $1$ and $y^3+1$; the first factor gives no solution; whereas the second factor leads to $(x,y)=(y^2,y)$, which is a solution for all $y\in\mathbb N$. Now suppose $xy+1$ is a nontrivial factor of $y^3+1$. Note that if $xy+1$ is a factor of $y^3+1$ which is $1\pmod{y}$, then so is $\frac{y^3+1}{xy+1}$, so we can assume WLOG $xy+1\le \sqrt{y^3+1}<y^{\frac{3}{2}}+1\implies $ $x<y^{\frac12}\implies x^2<y.$ Then $$k=\frac{x^2+y}{xy+1}\le \frac{2y}{x y+1}\implies kxy+k<2y....(\star )$$But if $k\ge 2$, then $kxy+k\ge 2y+2>2y$, contradicting $(\star)$. So $$k=1\implies x^2+y=xy+1\implies x^2-xy+y-1=0\implies (x-1)(x-y+1)=0.$$The lemma is now immediate. $\square$ Coming back to the main problem, we note that by our lemma, the only positive integer values that $\frac{x^2+y}{xy+1}$ can take are: $$\left\{\begin{array}{lc}\text{For} (x,y)=(a^2,a), & \frac{x^2+y}{xy+1}=a\\ \text{For} (x,y)=(1,a), & \frac{x^2+y}{xy+1}=1\\ \text{For} (x,y)=(a-1,a), & \frac{x^2+y}{xy+1}=1.\end{array}\right.$$So if $a\ne 1$, then $\frac{x^2+y}{xy+1}$ takes the value $a$ only once: for $(x,y)=(a^2,a)$. But it takes the value $1$ for infinitely many pairs, so the only possible integer is $\boxed{1}$.
02.06.2016 10:14
We will prove that $1$ is only solution. Let $\frac{x^2+y}{xy+1}=n$. For $n=1$, just take $x=1$ and arbitrary $y$. Now for $n > 1$ we have solution $(x,y)=(n^2,n)$. Now we will prove that there aren't any more solution for $\frac{x^2+y}{xy+1}=n$ $\iff$ $x^2+y=nxy+n$ $\iff$ $x^2-nyx+(y-n)=0$. This is quadratic equation w.r.t $x$, so it's discriminant must be perfect square i.e $\Delta = n^2y^2-4(y-n)$. We have $(ny-2)^2=n^2y^2-4ny+4 < n^2y^2-4y+4n$ which is true for $n>1$. Also $(ny+2)^2=n^2y^2+4ny+4 > n^2y^2-4y+4n$ which is also true, thus $(ny-2)^2 < \Delta < (ny+2)^2$. Thus we have $3$ possibilities for $\Delta$ i.e $\Delta= n^2y^2-4(y-n)=(ny-1)^2,(ny+1)^2,(ny)^2$ $1.$ case $\Delta=n^2y^2-4(y-n) = (ny-1)^2 =n^2y^2-2ny+1$, obviously parity contradicts this $2.$ case $\Delta=n^2y^2-4(y-n) = (ny+1)^2 =n^2y^2+2ny+1$, also parity $3.$ case $\Delta=n^2y^2-4(y-n) = (ny)^2 $ yields $y=n$ and $x=n^2$ which is only solution.
02.06.2016 10:40
If $x+1\le y$ then $xy+1=(x-1)y+1+y\ge (x-1)(x+1)+1+y=x^2+y$,so $\frac{x^2+y}{xy+1}\le 1$,which forces $\frac{x^2+y}{xy+1}=1$ i.e. $y=x+1$. If $x=y$,then $x^2+1|x^2+x$,so $x^2+1|x-1$.But $x-1<x^2+x$,which forces $x=1$,so $x=y=1$ i.e. $\frac{x^2+y}{xy+1}=1$. If $x>y$,then $xy+1|x^2+y\implies xy+1|x^2y+y^2\implies xy+1|(x^2y+y^2)-x(xy+1)=y^2-x.$ But $|y^2-x|\le\max\{y^2,x\}<xy+1$,because $xy+1>x$ and $xy+1>y^2+1>y^2$,which forces $y^2=x$ i.e. $\frac{x^2+y}{xy+1}=y$. Hence $\frac{x^2+y}{xy+1}=1$ for $(x,y)=(t,t+1),(1,1),t\in\mathbb{Z}_{+}$,while $\frac{x^2+y}{xy+1}=\ell$ for $(x,y)=(\ell^2,\ell)$. Therefore the answer is $1$.
18.04.2018 10:35
Could Vieta Jumping work?
22.06.2021 18:49
@above Yes, here is my solution: Let $\frac{x^2 + y}{xy + 1} = k$. Rearranging we get $x^2 - kxy + (y - k) = 0$. Now let $(x,y) \in \mathbb{N}^2$ be the solution to this equation which minimizes $x$. Let the other root be $x_1 \in \mathbb{Z}$. By Vieta we have $x + x_1 = ky$ and $xx_1 = y-k$. Now if $y - k = 0$, we have $(x,y) = (k^2 , k)$ which is a solution for every $k \in \mathbb{Z^+}$. If $y - k < 0$, then since $x > 0$, we have $x_1 < 0$, so $y^2 < ky = x + x_1 < x \implies x > y^2$. But note that $xy + 1 \mid x^2 + y \implies xy + 1 \mid x^2y + y^2 \implies xy + 1 \mid y^2 - x$. Since $x > y^2$, we must have $xy + 1 \leq x - y^2 \implies xy + y^2 + 1 \leq x$, but that is clearly a contradiction. If $y - k > 0$, then $x_1 > 0$. By our assumption, $x_1 \geq x$. Now note that $2x \leq x + x_1 = ky < y^2$, implying $x < y^2 / 2$. Now note that $xy + 1 \mid y^2 - x \implies xy + 1 \leq y^2 - x \implies x(y+1) < x(y+1) + 1 \leq y^2 \implies x \leq y - 1$. We have $ky = x + x_1 \leq x_1 + y - 1 \implies x_1 \geq ky - y + 1$. So, $y - k = xx_1 \geq x(ky - y + 1) \geq (ky - y + 1) \implies k(y+1) \leq 2y - 1 \implies k \leq 2 - \frac{3}{y+1} < 2$. For $k = 1$, it is easy to see that the pairs $(1,a)$ work for all $a \geq 1$, thus the only answer is $k = 1$.
25.12.2021 00:21
Discriminant