Question about infinite descent method in this proof How do we conclude that:"We have therefore constructed another pair $(a_1, b_1)$ in $S(c, k)$ with $a_1 + b_1 < a + b$. However,
$S(c, k)$ is contain in $Z^+ × Z^+$, so using the argument of infinite descent, we obtain our desired contradiction." in the top of page 4?
link: http://projectpen.files.wordpress.com/2008/03/pen06s.pdf
 A: The argument of infinite descent relies on the fact that you cannot find an infinite descending chain of positive integers. That is, for any positive integer $k$, there are only finitely many positive integers strictly smaller than $k$.
The arguments by "infinite descent" usually take one of two forms:


*

*The "minimal counterexample" form: you want to prove that all objects of interest satisfy a property $P$. You show that to every object that does not satisfy the property $P$ you can associate a positive integer. You then assume that there is at least one object that does not have property $P$ and argue by contradiction: you consider an object that fails to have property $P$ and has the smallest possible associated positive integer (a "minimal counterexample", sometimes called a "minimal criminal"). You then show that from assuming such a counterexample exists,  you can construct another counterexample which has strictly smaller associated positive integer . This contradicts the minimality of the original counterexample, and by this contradiction you conclude that no counterexample exists.

*The "infinite descent form". You again assume that there is some object that fails to have property $P$, and has a positive integer $n_1\gt 0$ associated to it. You show how this assumption allows you to find another object that fails to have property $P$, but with associated integer $n_2$ strictly smaller than $n_1$: $n_1\gt n_2\gt 0$. Then you can apply the argument to this second object to get a third, with $n_1\gt n_2 \gt n_3 \gt 0$. Continuing this way, we would be able to find an arbitrarily long ("infinite") descending sequence of positive integers. But this is impossible; the contradiction shows our assumption that some object fails to have the property is incorrect.
An example of the first type is the proof of the 4-color map theorem: it is shown that any if you had a smallest possible graph that cannot be colored with 4 colors, then you would be able to find an even smaller graph that cannot be colored with 4 colors, a contradiction to the fact that we started with the "smallest possible" counterexample.
An example of the second type was Fermat's proof that there are no positive integer solutions to $x^4 + y^4 = z^2$. He shows that if you can find integers $(x,y,z)$ such that $x^4+y^4=z^2$ and all are nonzero, then you can find another triple $(x_2,y_2,z_2)$ with $x_2^4 + y_4^2 = z_2^2$, but with $0\lt z_2\lt z$. You could then repeat this process to get a third triple $(x_3,y_3,z_3)$ with $0\lt z_3\lt z_2\lt z$, and so on. You cannot repeat this indefinitely, but the construction shows you can. The contradiction means that you cannot find the first triple $(x,y,z)$.
The particular problem linked is of the second type. We want to show that if $a$ and $b$ are positive integers, and $ab+1$ divides $a^2+b^2$, then $(a^2+b^2)/(ab+1)$ is a perfect square. So we assume that this is false, and there is some $k$ that is not a perfect square, and for which there is at least one pair $(a,b)$ with $a$ and $b$ positive integers, such that $ab+1$ divides $a^2+b^2$, and 
$$\frac{a^2+b^2}{ab+1} = k.$$
To each such pair $(a,b)$, let's associate the "size" $a+b$. We will show that given any pair $(a,b)$ with $(a^2+b^2)/(ab+1)=k$, we can find another pair $(a',b')$ with $(a'^2+b'^2)/(a'b'+1) = k$, but with $0\lt a'+b'\lt a+b$. This will show that if you can find a single example, you would be able to find an arbitrarily long sequence of examples, but each one would give you a smaller and smaller positive value of $a+b$, giving a contradiction.
Suppose $(a^2+b^2)/(ab+1) = k$. We may assume $a\geq b$, since $a$ and $b$ play symmetric roles. We look at the equation
$$x^2- kbx +b^2 - k = 0.$$
This equation has at least one integer solution (namely, $x=a$); since all coefficients are integers, the second solution must also be an integer (it must be a rational, since multiplied by $a$ we get $b^2-k$, and by the Rational Root Test it must be an integer). Call it $a_1$. Then
$$a_1^2 +b^2 = k(ba_1 + 1),$$
so $ba_1 + 1$ divides $a_1^2+b^2$, and $(a_1^2+b^2)/(ab_1 + 1) = k$. We want to show that $0\lt a_1\lt a$, because this will give us our "descent".
Since $x^2 - kbx + (b^2-k) = (x-a)(x-a_1) = x^2 - (a+a_1)x + aa_1$, we cannot have $a_1=0$, because $k$ is not a square (by assumption), so $b^2-k\neq 0$, yet $aa_1=b^2-k$. So $a_1\neq 0$.
And if $a_1\lt 0$, then notice that $-a_1kb \geq kb$ (since $a_1\lt 0$ is our assumption), so since $a_1^2 - kba_1 + b^2 - k =0$, we have
$$ k = a_1^2 - kba_1 + b^2 \geq a_1^2 + kb + b^2 \gt kb \geq k,$$
which is impossible ($k$ cannot be strictly larger than $k$). So that means that we must have $a_1\gt 0$.
Finally, since $aa_1 = b^2-k$, then $a_1 = \frac{b^2-k}{a}$. And since $a\geq b$, then $b^2-k \lt b^2 \leq a^2$, so $$a_1 = \frac{b^2-k}{a} \lt \frac{a^2}{a} = a.$$
This shows that $0\lt a_1\lt a$, and yet $(a_1,b)$ is another pair that satisfies our assumptions.
This shows that if we could find a single pair of positive integers $(a,b)$ such that $(a^2+b^2)/(ab+1)$ is an integer but not a perfect square, we would be able to find an infinite descending sequence of integers $0\lt \cdots \lt a_2 \lt a_1\lt a$. This is impossible, so there is no such pair.
