# Let $x$ and $y$ be positive integers such that $xy \mid x^2+y^2+1$.

Let $x$ and $y$ be positive integers such that $xy \mid x^2+y^2+1$. Show that $$\frac{x^2+y^2+1}{xy}= 3 \;.$$ I have been solving this for a week and I do not know how to prove the statement. I saw this in a book and I am greatly challenged. Can anyone give me a hint on how to attack the problem? thanks

-
xy|x2+y2+1 means? –  Chandra Sekhar Mar 1 '12 at 14:25
Hint: Have you see artofproblemsolving.com/Wiki/index.php/1988_IMO_Problems/… ? This yields to a similar attack. –  David Speyer Mar 1 '12 at 14:28
$xy$ divides$x^2+y^2+1$ –  Keneth Adrian Mar 1 '12 at 14:28
@DavidSpeyer, thanks for the link.. will study on it..:) –  Keneth Adrian Mar 1 '12 at 14:34
It seems that the solutions with $x>y$ are $x=F_n$, $y=F_{n+2}$ with $n$ odd, that is, $F_n^2+F_{n+2}^2 + 1= 3 F_{n}F_{n+2}$ when $n$ is odd. Is this a well-known Fibonacci identity? –  lhf Mar 1 '12 at 16:00

Use the very tricky technique called Vieta Jumping.
The idea is considering a polynomial $f(x,y)$ that is quadratic in both $x$ and $y$, with integer coefficients and symmetrical (that is $f(x,y)=f(y,x)$. We have that if $f(x,y)$ has some property when $x,y$ are integers and we want to prove something regarding $x$ and $y$. Suppose that some pair $x_1,y_1$ of integers satisfies the property, since $f$ is symmetrical, we can suppose WLOG that $x_1>y_1$ (the case $x_1=y_1$ is usually easy).

Recall the vieta formulas:
If $z_1$ and $z_2$ are the roots of $x^2+bx+c=0$, then $z_1z_2=c$ and $z_1+z_2=-b$.
Those formulas are very useful, particularly the last one, since it is a simple sum.

Now since $f(x,y)$ is quadratic in $x$, we apply the vieta formulas in $x_1$ and we find some integer $x_0$ with $x_0<y_1$ that satisfy the same property, Now we do the same with $y_1$ and find another integer $y_0$ with $y_0<x_0$ that also satisfy the property. Continuing this way we get a pair $(a,b)$ of integers that satisfy the property with $a$ and $b$ really small (like $a=1$). It's easy to prove what we want when the integers are small. Now since all these pairs were satisfying the same property, what we proved about $(a,b)$, also applies to the initial $(x_1,y_1)$.

Well, that was kinda long. I hope i have explained the main point. Try to use this on the problem and then back and post your results :)

-
+1: In case people are wondering how, check out the second example (which is exactly this problem!) on the wiki page on Vieta Jumping: en.wikipedia.org/wiki/Vieta_jumping#Example_2 –  Aryabhata Mar 1 '12 at 21:44
Beautiful - I wasn't not aware of Vieta Jumping before! –  Jason DeVito Mar 2 '12 at 2:04

Suppose $xy\mid x^2+y^2+1$ and let $t=\displaystyle\frac{x^2+y^2+1}{xy}$ such that $t\in\mathbb{N}$.

Construct the set, $$S=\left\{(x,y)\in\mathbb{N}\times\mathbb{N} : \frac{x^2+y^2+1}{xy}=t\in\mathbb{N}\right\}$$

We deduce that $\displaystyle\frac{x^2+y^2+1}{xy} \ge 3$ because $\displaystyle\frac{x^2+y^2+1}{xy}<3$ implies $x^2+y^2+1 \le 2xy \le x^2+y^2$ which is clearly a contradiction. Now fix $t$ and suppose that $t>3$. Since $S\neq \varnothing$, we can choose $(a,b)\in S$ such that $a+b$ is minimal and $t>3$. WLOG assume $a\ge b>0$. Let us consider the quadratic

$$p(w)=w^2-tbw+b^2+1=0$$

It follows that $a$ is a solution since $(a,b)\in S$ and hence satisfies the quadratic equation, that is $a$ is a root. By applying Vieta's formulas we obtain the other root $c$. Hence $a+c=tb$ and $ac=b^2+1$. Since $c=tb-a$ we have $c\in\mathbb{Z}$. Now it remains to prove that $(a,c)\in S$.

To this end suppose $c<0$. It follows that $$\displaystyle 0<a^2+ac+1-3ab=a^2+ac-\frac{3c}{t}(a+c)<0$$ which is clearly a contradiction. It also immediately follows that $c\neq 0$ as this implies $b^2+1=0$. Therefore $c\in\mathbb{N}$ and $(a,c)\in S$.

Now we show that this $c$ contradicts the minimality of $a$, that is $c<a$. Suppose $c>a$ so it follows that $a+1\le c$. But from Vieta's equations we obtain $\displaystyle a+1\le c=\frac{b^2+1}{a}\le a+\frac{1}{a}$ which is impossible since this inequality holds in $\mathbb{N}$ if and only if $a=1$ and hence $a=b=1$ implying $t=3$ which contradicts our assumption that $t>3$. Therefore $c\le a$. But if $c=a$ then this implies that $\displaystyle a^2=b^2+1>\frac{9}{4}b^2$ which again is a contradiction. Hence we conclude that $c<a$ and as a result $c+b$ contradicts the minimality of $a+b$. Hence $t=3$

-

I found this on Wolfram under the Fibonacci Number page:

http://mathworld.wolfram.com/FibonacciNumber.html

Catalan's Identity:

$F(n)^2 - F(n-r)F(n+r) = (-1)^{(n-r)}F(r)^2$

For $r = 1$, n is even

$F(n)^2 - F(n-1)F(n+1) = -1$

Replace F(n) using $F(n) = F(n+1) - F(n-1)$ and you get

$(F(n+1) - F(n-1))^2 - F(n-1)F(n+1) = -1$

or

$F(n+1)^2 + F(n-1)^2 + 1 = 3F(n-1)F(n+1)$

is of the form:

$x^2 + y^2 + 1 = 3xy$

I do not believe it shows that only Fibonacci numbers are solutions. The relationship that I was looking for on my other solution uses Catalan's Identity, with r = 2.

-

My try(wrong, post factum)

$$\frac{x^2+y^2+1}{xy}=k$$

Or:

$$\frac{x}{y}+\frac{y}{x}+\frac{1}{xy}=k$$

Now, we try to bound that integer:

Edit:

$$?>\frac{x}{y}+\frac{y}{x}+\frac{1}{xy}\geq\frac{3}{\sqrt[3]{xy}} \ \ \ \ \ (1)$$

We should deduce that $k=3$

$(1)$-GM

-
What about $x=1,k=4$? Then $x^2+y^2+1=18>3\times 1\times 4=3xy$. –  Alex Becker Mar 1 '12 at 16:30
Your AM-GM goes the wrong way. I am skeptical that anything like this can work: $(x^2+y^2+1)/(xy)$ can take plenty of values larger than $3$; those values just aren't integers. –  David Speyer Mar 1 '12 at 16:30

$x$ divides $x^2 + y^2 + 1$ implies $y^2 = ax - 1$.

Then $y$ divides $x(x+a)$

Case 1 - $y$ divides $x$, so $x = by$.

$$1/b + b + 1/(by^2) = k$$.

$$b=x=y=1$$

$$k=3$$

Or, $b=x=2$, $y=1$, $k=3$

Case 2 - $y$ divides $x+a$, so $y = -a \text{ mod } x$, $y^2 = 1 \text{ mod } x$.

$$x^2 + y^2 +1 = 2 \text{ mod } x$$

$x$ is $1$ or $2$. (Otherwise, $x$ does not divide the equation)

If $x = 1$, $x^2 + y^2 +1 = 2 \text{ mod } y$, $y$ is $1$ or $2$

If $x = 2$, $y$ is $1$ or $5$.

Solutions: $(1,1),(2,1),(5,2)$, $k$ is always $3$

(Tough to type on the phone)

-
Interestingly I got back to my computer and found (5,13) was also a solution, found by the same algorithm, plugging 5 in for x. Plugging in 13 etc, I get the solution (13,34) (34,89) (89,233). Hmmm. More work needed. –  Michael Sink Mar 1 '12 at 20:33
As they have pointed out, this has to do with Fibonacci numbers. Also, I edited your answer. –  Pedro Tamaroff Mar 1 '12 at 20:41
Thanks for the edit, Peter. I've found one error already, checking to see if that generates the rest of the sequence. –  Michael Sink Mar 1 '12 at 20:56
Nope, my equation falls apart. Interesting that it generated 3 solutions. –  Michael Sink Mar 1 '12 at 21:24
Your cases 1 and 2 aren't exhaustive. For example, 6 divides the product of 2 and 2+1; but it divides neither of them. –  John Bentin Mar 1 '12 at 21:48