Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
xy|x2+y2+1 means? –  Chandra Sekhar Mar 1 '12 at 14:25
1  
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
1  
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

5 Answers 5

up vote 9 down vote accepted

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 :)

share|improve this answer
3  
+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
1  
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$

share|improve this answer

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.

share|improve this answer

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

share|improve this answer
    
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
2  
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)

share|improve this answer
    
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
2  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.