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

Solution 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$.

Solution 2:

My reading of your objection is slightly different from anon's, so I thought I'd offer another answer. If I understand correctly, what you are saying is that, while $k=b^2$ would certainly contradict the statement

(1) "$k$ is not a perfect square",

it does not contradict the statement

(2) "$c$ is a positive integer implies that $k$ is not a perfect square"

since $k=b^2$ was derived under the assumption that $c=0$.

My answer to this is that it really is (1) and not (2) that is being assumed in the two proofs you cite. In fact, I'm not even sure where you get the idea that the proofs make the hypothesis that $c$ is a positive integer. It is simply the "other root"; there is no reason why $(c,b)$ must be an element of $S(k)$, or indeed, why $c$ must satisfy any property other than being a root. In fact, $c$ is initially not even assumed to be an integer - otherwise why the need to invoke Vieta's formulas? In both proofs, it eventually ensues that $c$ is a positive integer, and hence that $(c,b)\in S(k)$, but nothing like this is assumed at the outset.

I would add that, if you were correct that the proofs were assuming $c$ to be positive, then there would be no need to prove $c\ne0$ in the first place, since that would already be true by assumption.

Finally, I would point out that defining "natural number" to include both zero and positive integers would not materially alter the overall argument. The aim is to show that the sets $S(k)$ are empty if $k$ is not a perfect square. If $S(k)$ for non-perfect-square $k$ is empty when natural numbers are defined to be positive, it is still empty when they are defined to include zero. The reason is that letting $a$ and/or $b$ equal zero in the expression $\frac{a^2+b^2}{ab+1}$ clearly results in a perfect square. Therefore the extra ordered pairs in which one of both of $a$ and $b$ is zero all lie in $S(k)$ for which $k$ is a perfect square.

I don't know whether enlarging the definition of natural number to include zero would make the proof clearer or more acceptable to you, but if it would, there is no harm in doing so.

Addendum in response to OP's reply: Is something omitted from this text?

So I guess here is why I think that even though clearly if $c=0$ then $k=b^2$ is obviously a square, analogous to the argument with the other proof I've just given, then $(c,b)\not\in S(k)$ doesn't contradict that $k$ such that $ab+1|a^2+b^2$ for $a,b\in\mathbb{N}$ since $c\not\in\mathbb{N}$.

By my reading there should be an additional verb or phrase after "such that" and before "since". I'll try to give an answer anyway, since I believe that the confusion stems from the belief that there are some top-level assumptions being made about $c$, when in fact there are not. We do impose top-level assumptions on $a$ and $b$. But $c$ is not some object taken from the universe of objects satisfying the same assumptions as $a$ and $b$; it is just a number determined by $a$ and $b$ through a quadratic equation. (In the end it turns out, in the first linked proof, that $c$ satisfies all of the assumptions that $a$ does, except that it is less than $b$. This, however, is a deduction, not an imposed requirement.)

To recapitulate: we aim to show that there are no natural numbers $a$ and $b$ such that $\frac{a^2+b^2}{ab+1}$ is integer but not perfect square. The top-level assumption that the two cited proofs make, seeking a contradiction, is that there are such $a$ and $b$, with $a\ge b$. The value of $k$ is then fixed by $a$ and $b$, just as $k$ is a fixed number in the third proof you offer. Since at this point in the proof, $a$, $b$, and $k$ are just fixed numbers, then we can talk about the properties of the fixed polynomial $x^2-kbx+b^2-k$. In particular, we can talk about its other root $c$, which is also fixed, since it is completely determined by the polynomial. One property of $c$ that we are able to deduce is that it is non-zero, since, if it were zero, that would contradict a known property of the fixed number $k$, namely that it is not a perfect square.

In general I think there can be some unease with proofs by contradiction, especially if you know alternate proofs or have good understanding of the structure of the object under consideration. This unease comes about because you may, before reaching the desired contradiction, encounter statements that don't jibe with the other knowledge you have. You may feel that these statements invalidate the proof. The cure for this to suspend disbelief for the purposes of the proof. You can't allow that other knowledge in if you are trying to reprove the statement from first principles. It is actually completely expected that if, seeking a contradiction, you assume the existence of solutions that turn out to be impossible, you find in the working that these impossible solutions have properties inconsistent with those of solutions that are possible. Operating in suspension-of-disbelief mode, however, those inconsistencies shouldn't be considered manifest until you manage to arrive at a statement plainly in contradiction with assumptions internal to the proof.

Addendum II: While I'm correcting some typos, I'll take one more stab at making this clear. Given numbers $a$ and $b$, the numbers $k$ and $c$ are determined ($k$ by its definition, $c$ by Vieta's formula). If you have made assumptions about $a$ and $b$, you may be able to conclude something about $k$ and $c$. In both the first linked proof and the third proof - the one that you describe in your reply - we assume that $a\ge b$, that $a$ and $b$ are positive (taking anon's correction to the third proof) integers, and that $a$ and $b$ are such that $k$ is an integer. These assumptions imply that $c$ is a non-negative integer.

In the first linked proof, we further assume that $a$ and $b$ are such that $k$ is not a perfect square. From this further assumption it follows that $c\ne 0$. In the third proof, there is a different further assumption, namely that $b$ is positive and minimal. From this different further assumption we conclude that $c=0$. Different additional assumptions lead to different conclusions about the value of $c$.

Solution 3:

The proof does not require contradiction or any working hypothesis about $k$ being a square or not.

It can be presented as an algorithm for taking an integer solution $(a_1,b_1)$ with $a_1b_1 \neq 0$ and producing an integer solution $(a_2,b_2)$ that is smaller. Repeating this reduction process, eventually there will appear a solution $(a_n,b_n)$ with $a_nb_n=0$. The proof that the algorithm is correct requires $k$ to be an integer, but no other arithmetic condition such as being a square. When the smallest solution is reached, with one of the variables equal to $0$, this demonstrates that $k$ (which is constant during the execution of the algorithm) was a square, but the algorithm and the correctness proof were blind to that.

To illustrate, imagine observing the reduction procedure starting from a pair of giant numbers $(A,B)$. Before running the reduction process one might want to calculate $\frac{A^2 + B^2}{AB+1}$ to see that it is really an integer. This calculation will output an integer so large that it is not immediately recognizable as a perfect square. The reduction process will then produce a sequence of smaller pairs $(A_i, B_i)$ eventually reaching $(n,0)$ for some $n$ and then the square nature of $k$ will be apparent.

As this outline may suggest, there is something suspicious when...

to show that c≠0 then we must finally use the assumption that k is not a perfect square.

There is no reason to show that $c \neq 0$ at any stage of the proof. The quotation is describing the situation after reduction from $(a,b)$ to a smaller solution $(b,c)$. Having $c=0$ is the goal of the argument. The only thing that needs to be proved is $c \geq 0$ (so the process can continue) and that $(b,c)$ is smaller than $(a,b)$ (so that the algorithm has made progress). Once the new pair $(b,c)$ has been constructed, if $c=0$ the algorithm stops successfully, and if $c > 0$ it continues the reduction process.