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.

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

share|improve this question
    
Do you want to know how the technique of infinite descent works generally? Or do you have a question about this particular proof? –  Srivatsan Nov 2 '11 at 2:34
    
@Srivatsan - i want to know how the infinite decent work generally and in that special case –  Victor Nov 2 '11 at 2:37

1 Answer 1

up vote 5 down vote accepted

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:

  1. 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.

  2. 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.

share|improve this answer

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.