[Math] Seemingly invalid step in the proof of $\frac{a^2+b^2}{ab+1}$ is a perfect square

Question

Recall the famous IMO 1988 question 6:

Suppose that $\displaystyle\frac{a^2+b^2}{ab+1}=k\in\mathbb{N}$ for some $a,b\in\mathbb{N}$. Show that $k$ is a perfect square.

Solutions can be found:

$1)$ http://projectpen.files.wordpress.com/2008/10/pen-vol-i-no-1.pdf (Section 2.6)

$2)$ http://www.georgmohr.dk/tr/tr09taltvieta.pdf

When I first saw solutions to this problem I had no reluctance in accepting the validity of solutions, but just recently I read over them again and there seems to be several things bugging me and it all relates to a particular step in all solutions above.

Solutions $1)$ and $2)$ are essentially the same argument in the sense that they both assume firstly that $k$ is not a perfect square and then deduce a contradiction.

Now let us get to the issue at hand. It follows from Vieta's formulas that the other root $c$ (the other root is called $a_1$, $x_2$ in $1)$, $2)$ respectively – I'm just going to call it $c$ for simplicity as a general reference to the other root of $x^2-kbx+b^2-k$ where $a$ is the first root) must be an integer. Now note that in proving that $c\ge 0$ for $1)$ and $2)$ we didn't need to use the assumption that $k$ is not a perfect square. But to show that $c\neq 0$ then we must finally use the assumption that $k$ is not a perfect square. Here is where there seems (at least to me at the time being) to an issue. Recall that in the problem we want $a,b\in\mathbb{N}$, so this is equivalent to defining a set where we fix $k$.
$$S(k):= \left\{(a,b)\in\mathbb{N}\times\mathbb{N} : \frac{a^2+b^2}{ab+1}=k\in\mathbb{N}\right\}$$

Now in $1)$ and $2)$ they assume that $k$ is not a perfect square and hence deduce that $c\neq 0$ because if $c=0$ then as a result from $x^2-kbx+b^2-k=0$ then $k=b^2$. Here is where there seems to be an invalid contradiction. If $c=0$ then it doesn't contradict that $k=b^2$ because $c=0\not\in\mathbb{N}$ and hence $(c,b)\not\in S(k)$ so as a result $c^2-kbc+b^2-k=0$ no longer satisfies the condition of the question and hence doesn't contradict anything even though $k=b^2$. This is where there may be something I misunderstood and it would be great if someone can justify with clarity as to why my reasoning is flawed?

A little note: We see that it was deduced in $1)$ and $2)$ that $c<a$ just by using the assumption that WLOG $a\ge b$ along with Vieta's formulas ($c<b$ can also be proven just by these assumptions alone). So proving $c<a$ and $c<b$ was independent of $(c,b)\in S(k)$ and is also independent of assuming some minimality property on $b$. Hence we can say that $c<a$ and $c\ge 0$ are all deduced without assuming $k$ not being a perfect square nor $b$ being minimal for fixed $k$.

Answer 1

First, note that in (2), the naturals $\Bbb N$ are referred to as "nonnegative integers" (page one) which certainly includes $0$. But that is not the crux of the confusion here.

If $c=0$ then it doesn't contradict that $k=b^2$.

Nobody claims that "$c=0$" contradicts "$k=b^2$." Rather, it contradicts our original hypothesis that the integer $k$ is not a perfect square (clearly $b^2$ is a square!). The flow of the argument goes like this:

• Hypothesis (H): $k$ is not a perfect square and $S$ is nonempty.
  • Givens (G): Wlog, let $(a,b)\in S$ with $a>b$ and $a+b$ minimal among $S$.
  • Deduction 1: Quadratic formula says $\frac{x^2+b^2}{xb+1}=k$ has a root $x=c$ in addition to $x=a$.
  • Deduction 2: By Vieta's $c=kb-a$ so $c$ is an integer.
  • Hypothesis A: $c=0$.
    • Deduction: Plugging $x=c$ the equation gives us $b^2=k$
    • Contradiction: This contradicts our top-level assumption that $k$ is not a square.
  • Deduction 3: $c\ne 0$.
  • Hypothesis B: $c<0$.
    • Deduction: $c^2-kbc+b^2-k\ge c^2+k(1)+b^2-k=c^2+b^2>0$.
    • Contradiction: But the above is $0$, as it is $c$ plugged into the quadratic.
  • Deduction 4: $c>0$, and so $(c,b)\in S$.
  • Deduction 5: Since $a>b$, $b^2-k<a^2$, so $c=\frac{b^2-k}{a}<a$ hence $c+b<a+b$.
  • Contradiction: Deduction 5 contradicts the given that $a+b$ was minimal among pairs.
• Deduction X: Either $S$ is empty or $k$ is a perfect square.

This is just a rough outline that concisely presents the structure of the argument. Notice that this amounts to a proof-by-contradiction which contains proofs-by-contradiction. Let me know if you have any questions about the dependencies between these hypotheses and deductions!

Remark. Technically in Deduction 1 we don't know whether or not $c\ne a$, but we don't need to know either. The rest of the argument works just the same, until Deduction 5 where we learn that $c+b<a+b$, which is impossible if $c=a$ (not that it matters!).

---

I suspect your paraphrasing (or the book!) has a minor typo. Let me put it in bullet points.

• Fix $k$ to be some positive integer. Consider the set $Q$ of pairs $(a,b)$ such that $a\ge b\color{Red}>0$ and $$\frac{a^2+b^2}{ab+1}=k.$$
• Then $a$ is a root of the quadratic equation $\frac{x^2+b^2}{xb+1}=k$. Let $c$ be the other root.
• By Vieta's formulas, $a+c=bk$, so $c$ is an integer.
• We have $k(bc+1)=a^2+b^2>0$, so we must have $bc\ge -1$. Since $b> 0$, we have $c\ge 0$.
• Suppose $c>0$. Then the product of roots is $ac=b^2-k<b^2$, which is impossible unless $b>c$, and if $b>c$ then the valid pair $(b,c)\in Q$ has $c$ smaller than $b$ in $(a,b)$, contra minimality.
• Therefore, $c=0$ and $k=b^2$ is a square. Since our choice of $k$ was arbitrary, whenever $\frac{a^2+b^2}{ab+1}$ is a positive integer it must also be a perfect square.

Don't confuse this argument, say (3), with the arguments in the original two links.

• Both (1) and (2) assume $k$ is not a perfect square in order to derive a contradiction, while in (3) this is not assumed (though its negation is derived nonetheless).
• In (1), $S(k)$ is defined by strictly positive pairs, and the pairs are not ordered by size. We deduce $c\ne0$ here by invoking the assumption $k$ is nonsquare, and thus $(b,c)\in S(k)$.
• In (2), $S$ is defined to possibly contain pairs with one or both being $0$, though it also doesn't force the pairs to be ordered - the order of $A,B$ is taken wlog. We assume by hypothesis that no pair in $S$ has a $0$ and obtain a contradiction, so it does contain a $0$, implying $k$ is square.
• In (3), $Q$ contains strictly positive pairs, and they are ordered by size. Similar to (2) we prove that (using contradiction on minimality) $k=b^2$, even though $(b,0)\not\in Q$.

The arguments are subtly different and go about the proof in different ways. I would have advised you to stick to one of the proofs and understand that one before moving on to another, let alone two others, but the cat is out of the bag now I guess.

Concerning your perception of ambiguity, let me just say this. We desire to say that whenever $\frac{a^2+b^2}{ab+1}$ is a positive integer, it is a perfect square. In order to prove this, we could fix $k$ positive and consider all positive, or alternatively nonnegative, pairs $a,b$ such that the fraction equals $k$, and go from there; in the end our desired claim follows because our choice of $k$ to fix was arbitrary.

Note that in (3), the set $Q$ does not contain every pair $x,y$ such that $\frac{x^2+y^2}{xy+1}=k$. It only contains the positive ones. We prove that either $(b,c)\in Q$ and get a contradiction on minimality, or else $c=0$ and plugging it in gives $k=\frac{0^2+b^2}{b\cdot 0+1}=b^2$ is a square. Again, it does not matter that $(b,0)\not\in Q$, the computation is valid regardless because $c=0$ is still a root of $\frac{x^2+b^2}{xb+1}=k$, just not one inside $Q$.