The solution is given in Arthur Engel's Problem-Solving Strategies in Chapter 6, problem E15 if you have a copy. The solution does not look very simple; I had to read it a couple times to understand it.

For a fixed $k$, we denote $a_{0},b_{0}(a_{0}\ngeq b_{0})$ is a solution of this equation with $b_{0}$ smallest. Then $b_{0}$ is one root of this equation $b^{2}-ka_{0}b+a_{0}^{2}+k=0$ Then this equation has another root $b_{1}$ and $b_{1}=\frac{a_{0}^{2}+k}{b_{0}}, b_{1}=ka_{0}-b_{0}$, such that $b_{1}$ is a positive integer. Because $b_{0}$ is smallest, $b_{1}\geq b_{0}$, thus $a_{0}^{2}+k\geq b_{0}^{2}=ka_{0}b_{0}+k-a_{0}^{2}$ or $2a_{0}\geq kb_{0}$ $ka_{0}-b_{0}\geq b_{0}$ or $ka_{0}\geq 2b_{0}$ So $a_{0}=b_{0}$, then $k=\frac{2x^{2}}{x^{2}+1}$, so $k=1$

libra_gold wrote: Then $b_{0}$ is one root of this equation $b^{2}-ka_{0}b+a_{0}^{2}+k=0$ Shouldn't it be $b^{2}-ka_{0}b+a_{0}^{2}-k=0$ instead?

Sorry, I have made a mistake. Now it is correct. Suppose that $a_{0}, b_{0}$ is a solution in positive integers to $a^{2}+b^{2}= k(ab+1)$ with $a+b$ smallest. If $a_{0}= b_{0}$, then $2a_{0}^{2}= k(a_{0}^{2}+1)$. But that implies that $a_{0}= b_{0}= k_{0}= 1$. Now we may take $a_{0}< b_{0}$. Let $b_{1}$ is another root of the equation $b^{2}-ka_{0}b+a_{0}^{2}-k=0$. it implies that $a_{0}, b_{1}$ is also a solution. Then $b_{1}=\frac{a_{0}^{2}-k}{b_{0}}, b_{1}=ka_{0}-b_{0}$ Because $k=\frac{a_{0}^{2}+b_{0}^{2}}{a_{0}b_{0}+1}> \frac{b_{0}}{a_{0}}-\frac{1}{a_{0}}$, $b_{1}=ka_{0}-b_{0}\geq 0$, ie $b_{1}$ is a non-negative integer. But if $b_{1}>0$, then $b_{1}\geq b_{0}\to k\geq \frac{2b_{0}}{a_{0}}$. Because $\frac{a_{0}^{2}+b_{0}^{2}}{a_{0}b_{0}+1}<\frac{b_{0}}{a_{0}}+1$, it leads to a contradiction $b_{0}<a_{0}$. So $b_{1}=0$, then $k=a_{0}^{2}$.

I am afraid the solution still does not seem to be complete. You have shown that the minimal solution $(a_{0},b_{0})$ has the property $b_{1}=0$ and thus $k$ is a perfect square. But in fact the minmal solution is $(a_{0},b_{0}) = (1,1)$, so $k=1$, which is a perfect square. But what about non-minimal solutions? I think it is possible to adapt your proof to show that all solutions in positive integers have the given property.

$k$ is fixed in his considerations so $a_{0}=b_{0}=1$ is a minimal solution only for $k=1$.

infact its possible to find all sol a,b where a*a+b*b/ab+1=k*k

Let $(a,b)=d, \ p^{k}|ab+1,c=\frac{a^{2}+b^{2}}{ab+1},a_{1}=a/d,b_{1}=b/d$ and c is integer. Then $(d,ab+1)=1, p\not |a, a=x(mod \ p), b=y(mod \ p).$ It give $xy=-1(mod \ p), \ x^{4}+1=0(mod \ p).$ Therefore $a=x_{p}^{3}(mod \ p^{k}),b=x_{p}(mod \ p^{k}$ or $a=x_{p}(mod \ p^{k}),b=x_{p}^{3}(mod \ p^{k})$. It give solution $a=x^{3}, b=x$ or $a=x,b=x^{3}$, for these cases $c=x^{2}$.

Engel hyped this problem up a lot in his book making it sound horribly difficult. However, by today's standards I can't imagine this problem being anything higher than #2 on the IMO. Just look at problems like 2003 #2, or 2002 #3.

libra_gold wrote: Because $k=\frac{a_{0}^{2}+b_{0}^{2}}{a_{0}b_{0}+1}> \frac{b_{0}}{a_{0}}-\frac{1}{a_{0}}$, ${b_{1}=ka_{0}-b_{0}\geq 0}$. That is not true since $b_{1}=ka_{0}-b_{0}\geq 0$ if and only if $k\geq \frac{b_{0}}{a_{0}}$ and with $k=\frac{a_{0}^{2}+b_{0}^{2}}{a_{0}b_{0}+1}> \frac{b_{0}}{a_{0}}-\frac{1}{a_{0}}$ you can't say that $k\geq \frac{b_{0}}{a_{0}}$

Rust wrote: $x^{4}+1=0(mod \ p).$ Therefore $a=x_{p}^{3}(mod \ p^{k}),b=x_{p}(mod \ p^{k}$ or $a=x_{p}(mod \ p^{k}),b=x_{p}^{3}(mod \ p^{k})$. Sorry, but i didn't understand that part.How did you get that ?

I was also going to post it to the forum, but the solution could be easily FOUND! http://www.mathpages.com/home/kmath334.htm Very tricky indeed!

Sorry about reviving this old thread, but something's been bugging me. In Mathematical Olympiad Challenges, Titu Andreescu gives a pretty short and readily comprehensible proof that the pair $ (\alpha,\beta)$ with $ \alpha + \beta$ minimal produces a perfect square in $ \frac{a^2 + b^2}{1 + ab}$. However, I do not see how this shows that all possible $ (a,b)$ with $ \frac{a^2 + b^2}{1 + ab} \in \mathbb Z$ produce perfect squares.

I don't have the book, but the answer is: For *fixed k* with a+b minimal, we get a perfect square, so it works for all k.

kunterbunt wrote: For *fixed k* with a+b minimal, we get a perfect square, so it works for all k. Sorry, what do you mean by "fixed k" and how does it change the solution?

Truffles wrote: kunterbunt wrote: For *fixed k* with a+b minimal, we get a perfect square, so it works for all k. Sorry, what do you mean by "fixed k" and how does it change the solution? Think of the problem like this: for any integer $k$, if there exist integers $a$ and $b$ such that $k = \frac{a^2 + b^2}{1 + ab}$, then $k$ must be a perfect square. Suppose that $k = \frac{a^2+b^2}{1 + ab}$ for some positive integers $a$ and $b$. Then the set of all pairs of nonnegative integers $(a,b)$ for which $\frac{a^2 + b^2}{1 + ab} = k$ is non-empty. We can therefore find a pair of integers $(a,b)$ in this set that minimizes $a + b$. The bulk of this problem is showing that one of $a$ or $b$ in such a minimal pair $a+b$ must be 0, from which it follows that $k$ must be a perfect square.

Solution. (From IMO 1988 booklet) We set $\frac{a^2+b^2}{ab+1}=q\in \mathbb{N}$ and get $a^2+b^2=qab+q$. Since $a$ and $b$ occur symmetrically we may assume $a \le b$. Then \[ qa-a<b\le qa. \] Proof of the left-inequality. Suppose $b>qa$, then $b=qa+c$ with $c\in \mathbb{N}$. Thus \begin{align*} a^2+b^2=qab+q &\Longrightarrow a^2+(qa+c)^2 = qa(qa+c)+q \\ &\Longrightarrow a^2+q^2a^2+2qac+c^2 = q^2a^2+qac+q\\ &\Longrightarrow a^2+qac+c^2 = q \\ &\Longrightarrow q \le qac<a^2+qac+c^2 = q \\ &\Longrightarrow q<q, \end{align*} a contradiction! Thus $b\le qa$. From $qa-a<b\le qa$ we get $b=qa-r$ with $0\le r<a$ and $r\in \mathbb{N}_{0}$. From $a^2+b^2=qab+q$ we get \begin{align*} a^2+(qa-r)^2=qa(qa-r)+q &\Longrightarrow a^2+q^2a^2-2qar+r^2 = q^2a^2-qar+q \\ &\Longrightarrow a^2+r^2=qar+q \\ &\Longrightarrow a^2+r^2=q(ar+1) \\ &\Longrightarrow \frac{a^2+r^2}{ar+1}=q. \end{align*} Thus if one pair $(a,b)$ satisfies $\frac{a^2+b^2}{ab+1}=q$, then also the pair $(r,a)$ satisfies $\frac{r^2+a^2}{ra+1}=q$. But we have $0\le r<a\le b$, so that each component of $(r,a)$ is smaller than each component of $(a,b)$. Since there is no infinite strictly monotonic decreasing sequence of positive integers we will get smaller pairs until $r=0$. From $ \frac{a^2+r^2}{ar+1}=q$ and $r=0$ we get $q=a^2$. Thus $q$ is a square. This is also one of my favorite NT problem..

Generalisation: http://www.artofproblemsolving.com/Forum/viewtopic.php?f=56&t=349211

let $(a,b)$ be the minimum solution, it means that $a$ is minimum from all $a$ which can be solution for this problem let $k$ is a positive integer square and $a^2+b^2=kab+k=>f(x)=x^2-kxb+b^2-k$ $f(a)=0 f(a_1)=0$ $a_1=kb-a$ $a_1=\frac{b^2-k}{a}$ case :1 $a=kb=>a_1=0=>k=b^2$, which gives that $a=b^3=>\frac{a^2+b^2}{ab+1}=b^2$ case :2 $a<kb=>a_1\in\mathbb{N}=>k<b^2$ $f(b)=b^2-kb^2+b^2-k<0$[*] if [*] holds then we can say that $a_1<b<a=>a_1<a$ which is condraction!)

case :3 $a>kb=>a_1<0$ and $a_1$ is integer$=>a_1=\frac{k-b^2}{a}\in\mathbb{N}=>k\ge a+b^2>kb+b^2=>b=0$ which is condraction.

Same concept of descent, but maybe a little cleaner. Since $a^4+1 = (a^2)(a^2+b^2)-(ab-1)(ab+1)$, and $b^4+1=(a^4+1)b^4-(a^4b^4-1)$, we have that $ab+1 \mid a^2+b^2$ implies that $ab+1 \mid a^4+1$ which itself implies that $ab+1 \mid b^4+1$. So assume that $a \ge b$. Then if $ab+1 \mid a^4+1$, then we have $b^4+1=(ab+1)(bc+1)$, for integral $c$. Clearly $c < b$, and $bc+1 \mid c^4+1$. This means that there is some $d<c$ such that $cd +1 \mid d^4 +1$. We can continue to generate smaller and smaller pairs until we reach a zero. Working backwards, we can guess that the solutions are of the form $a_0=0, a_1=k, a_{n+1}=k^2a_n-a_{n-1}$, and indeed it straightforward to verify that this recursion generates the correct terms in the sequence given $a_0,a_1$, and that $k^2=(a_n^2+a_{n+1}^2)/(1+a_na_{n+1})$. I really like this problem, because if they had the initial condition less restrictive and thus "harder", i.e. $ab+1 \mid a^4+1$ instead of $ab+1 \mid a^2+b^2$, my guess is that a lot more contestants would have solved it correctly.

Hi guys I found in a NT book a stronger version of this problem. It says that the result is not just a square of an integer but GCD(a,b)^2. Can anyone give a proof??. Thanks in advance.

Well it was a hard problem in the late 80s. But now since vieta jumping is well known, it ain't that hard. P. S. Although Engel's solution is large and is hard to comprehend, the case with Titu's one is different.

This problem feels somewhat unsatisfying; compared to USA TST 2002/6, it's only patting the surface of quadratic infinite descents and not really diving in more logically. Suppose the assertion fails for some $(a, b)$ and pick $a+b$ minimal; WLOG $a \geq b$. In particular, let $$a^2+b^2=c(ab+1) \iff a^2-abc+b^2-c=0$$for some positive integer $c$. This means that if $(a, b)$ is a solution, so is $(a', b)$ where $a' = bc-a = \frac{b^2-c}a$. Notice furthermore that obviously $bc-a$ is positive, because else $$c \geq a+b^2 \implies a^2+b^2=c(ab+1) \geq (a+b^2)(ab+1) > a^2+b^2$$is a contradiction; we cannot have $a'=0$ either as $c$ is not a perfect square. Then $(a', b)$ works as well, and $$a' = \frac{b^2-c}a < a,$$contradicting minimality.

Although this is solved using Vieta Jumping, I made a Java Program (see attachment) to find some of the cases. MOST (NOT ALL) cases are here of type $(a, a^3)$ but that's isn't sufficient to prove the problem as $(8, 30)$ is a nontrivial solution. Also, you can prove that the perfect square is actually the square of GCD of $(a, b)$.

Note that if $b=0$, then $\dfrac{a^2 + b^2}{ab+1} = a^2$, a perfect square. Now suppose $\dfrac{a^2 + b^2}{ab+1} = k$. Fix $k$. We have a quadratic in $a$, $$a^2 - bk \cdot a + \left( b^2 - k \right) = 0$$Given a root for $a$, we can switch it to $\dfrac{b^2 - k}{a}$ and the quadratic still holds. Suppose $a \geq b$ at first. $$b = \dfrac{ab}{a} \leq \dfrac{b^2}{a} > \dfrac{b^2 - k}{a}$$ So now $b>a$, We proceed to flip $b$ by considering a similar quadratic in $b$. This eventually lead to one of $a,b$ being zero, thus the conclusion. Otherwise the process forms a infinite chain of decreasing pairs, So there exist a pair with exactly 1 of $a,b$ negative. This leads to $k \leq 0$, Impossible as $a,b \in \mathbb{Z^+}$ at first. Thus the Infinite Descent Method always works, the conclusion follows. $\hfill \square$

It is easy to see that $a \neq b$ (if otherwise, $\tfrac{2a^2}{2a+1}$ takes on positive integer value only at $a=1$). Let $k$ be arbitrary non-square integer. For the sake of contradiction, assume $\tfrac{a^2+b^2}{ab+1}=k.$ Let $a_1$ and $b_1$ denote the values such that $\tfrac{a_1^2+b_1^2}{a_1b_1+1}=k,$ such that $a_1+b_1$ is minimized. Without loss of generality, assume $a_1 > b_1.$ Fix $b_1$ and let $a_1=x$ to obtain $x^2+x(b_1k)+(b_1^2-k)=0.$ Obviously, one of the roots is $x_1=a_1,$ and the other root satisfies $x_2=b_1k-a_1$ and $x_2=\tfrac{b_1^2-k}{a_1}.$ The first condition implies $x_2$ is an integer, and the second condition implies $x_2 \neq 0,$ as $k$ is not a perfect square. Observe $\tfrac{x_2^2+b_1^2}{x_2b_1+1}=k,$ implying $x_2>0.$ From $a_1>b_1,$ it follows $x_2 = \tfrac{b_1^2-k}{a_1} < a_1.$ But this is a contradiction, since $a_1+b_1>x_2+b_1.$

solyaris wrote: I am afraid the solution still does not seem to be complete. You have shown that the minimal solution $(a_{0},b_{0})$ has the property $b_{1}=0$ and thus $k$ is a perfect square. But in fact the minmal solution is $(a_{0},b_{0}) = (1,1)$, so $k=1$, which is a perfect square. But what about non-minimal solutions? I think it is possible to adapt your proof to show that all solutions in positive integers have the given property. I think it's okay. We assumed the opposite - there are solutions such that k is not a square. Then we chose the minimum such solution - for example with the minimum sum a + b. Then, using the fact that k is not a square by proving that a and b are distinct, we obtain the solution (a, b1), where b1 is less than b but is still a positive integer and k is the same as for (a, b ), so it is not square. So this contradicts that (a, b) was a solution with k not square and the minimal sum of a and b, and if the minimal solution does not exist, there is none solution with k not square. This proves the result.

Clearly $a=b$ gives a perfect square as $a=b=1$ is the only possibility, implying that $\frac{a^2+b^2}{ab+1} = 1$. Now, let $(a_0,b_0)$ be the solution such that $a+b$ is minimized to $\frac{a^2+b^2}{ab+1} = k$ for any fixed non-square integer $k$ where WLOG $b_0>a_0$. Then, $a_0$ is a root of $a^2+(b_0k)a+(b_0^2-k)=0$. The other root to this equation is $a_1 = b_0k-a_0 = \frac{b_0^2-k}{a_0}$ which must be a positive integer. However, this contradicts the minimality of $a_0+b_0$, so no solutions to the equation exist for non-square $k$.

Thank you to @Pyramix for the Java program. Based on the additional cases I have constructed the set of cases $(a, b) = (x^3, x^5 - x)$ since the solution set $(a, b) = (x, x^3)$ is already known. I stared for a long time and did not find Vieta's Jumping intuitive. I am interested to hear your thoughts on characterizing the solution space of the problem. In general it seems like $$a, b \in Z_{>0}, (ab + 1)\ |\ (a^2 + b^2) \implies gcd(a, b)^2 = \frac{a^2 + b^2}{ab + 1}$$ Edit: as a separate note I would like to add that the logical considerations based on minimality of $a + b$ (such as Vieta's Jumping) are confusing with reference to contrapositive logic. Proof by contradiction allows us to yield proofs of the form $$(P \land Q \implies \lnot P) \implies \lnot Q$$ due to contrapositive logic, but since the claim is stated as an if-then (restricting to $a, b > 0$) I want to say we only have the option of proving $$\lnot Q \implies \lnot P$$ if not $$P \implies Q$$ Here, $P$ is the statement $$(ab + 1)\ |\ a^2 + b^2$$ and $Q$ is the statement $$\exists k : \frac{a^2 + b^2}{ab + 1} = k^2$$

Let $(a, b)$ be the the "smallest solution" in the sense that $a + b$ is minimized. Then we claim that if $k = (a^2 + b^2)/(ab + 1)$, then $\boxed{k = b^2}$. Also without loss of generality, assume $a > b$. Consider the quadratic $f(t) = t^2 - (kb)t + (b^2 - k)$. Then there are two roots $a, a_0$, and by Vieta we find that $a + a_0 = kb \in \mathbb{Z} \implies a_0 \in \mathbb{Z}$, and also that $aa_0 = b^2 - k$. Therefore if $(a, b)$ is a solution, we find that $\left(\frac{b^2 - k}{a}, b \right)$ is also a solution. Claim: $a_0 = 0$, so that $k = b^2$. Proof: Assume then we have $a_0 > 0$. Then since $a$ is minimal, we must have $a_0 > a$, or else we contradict minimality. Hence \begin{align*} &\frac{b^2 - k}{a} > a \\ \iff& b^2 - a^2 > k = \frac{a^2 + b^2}{ab + 1} \\ \iff& b^2(ab) > a^2(ab + 2), \end{align*}which is a contradiction. Therefore $a_0 = 0 \implies k = b^2$, as desired. $\blacksquare$

First, let's lay out the Vedic theorem: Theorem (Vedic theorem ) : establish $x_1, x_2$ forUnary quadratic equations $a x^2+b x+c=0$ of the roots, then there is $x_1+x_2=-\frac{b}{a}$ moreover $x_1 x_2=\frac{c}{a}$ Now that the tools are ready, let's get to work! moreover $a b+1 \mid a^2+b^2$ Confirmation $c \triangleq \frac{a^2+b^2}{a b+1}$ is perfectly squared. Proof that if $\mathrm{a}$ and $\mathrm{b}$ exist such that $\mathrm{c}$ is not perfectly squared, it can be constructedNon-empty collections ${ }^a S \subset \mathbb{N}^* \times \mathbb{N}^*$ make $\forall(a, b) \in S$ There is c that is not perfectly squared. according toThe principle of good order ${ }^a$ (well-ordering principle), you can know that there is $\left(a_0, b_0\right) \in S$ make $a_0+b_0$ The value is minimal. will $a_0, b_0$ Substituting C'sexpression ${ }^{\varrho}$ Get: $$ a_0^2-a_0 b_0 c+b_0^2-c=0 $$ Now consider a quadratic equation: $$ x^2-x b_0 c+b_0^2-c=0 $$ Know $a_0$ is one of the roots of the equation. according toFundamental theorems of algebra $^a$ (fundamental theorem of algebra), we can see that there is another root in this equation $a_1$ , and we can use Veda's theorem to get the relationship between the two: $$ \left\{\begin{array}{l} a_0+a_1=b_0 c \\ a_0 a_1=b_0^2-c \end{array}\right. $$ Without losing generality, we assume $a_0>b_0$, then due to $b_0 c$ and $a_0$ are all integers, $a_1$ is an integer. Because $\mathrm{c}$ is not perfectly squared, so $a_1 \neq 0$ 。 if $a_1<0$ Rule: $$ a_1^2-a_1 b_0 c+b_0^2-c \geq a_1^2+c+b_0^2-c>0 $$therefore $a_1$ as $a_0$ and $b_0$ are all positive integers Now according to the equation $\left({ }^*\right)$, it can be seen $a_1=\frac{b_0^2-c}{a_0}<\frac{b_0^2}{a_0}<a_0$ imply $a_1+b_0<a_0+b_0$ 。 However, this is contrary to the principle of good order, so $\mathrm{S}$ must be an empty set. So for all satisfied $a b+1 \mid a^2+b^2$ positive integers $a$ and $b, \frac{a^2+b^2}{a b+1}$ Always perfectly squared.

We can solve this problem using well ordering principle and arrive at a contradiction . I too have the same solution like Martin.s where i consider a set S, S={(a,b)∈ N X N : a^2+b^2/ab+1 is an integer and not a perf square} and show that this set S is empty(bad).