Monday, May 09, 2005

Infinite Descent

Pierre de Fermat was very proud of his technique known as Infinite Descent. He wrote that this method "will lead to marvelous advancement in the theory of numbers" (quoted from: http://fermat.workjoke.com/flt2.htm)

As he often did, Fermat left very few details on how to apply the method. He did provide one example of this method in his proof that the area of a right triangle cannot be equal to a square number. An elegant application of this proof is found in the case of FLT: n=4 where the proof rests on the method of infinite descent and the solution to Pythagorean Triples.

The basic method is very straight forward. One proves that if an assumption is true, it means that the assumption must also be true for an element that is smaller. In other words, an assumption leads to the proposition of an infinite number of cases where it is true.

This technique is especially useful in the domain of positive integers. In this case, infinite descent is impossible since it contradicts the Well Ordering Principle. In other words, there must always be a smallest element in any set of positive integers. But if there is a smallest element, then, there cannot be an infinite descent. In this way, the method can be used as way to prove by contradiction certain negative assumptions. It can also be used to prove a positive conclusion as I will show below.

Fermat is known to have used this technique to prove that there is no square equal to a right triangle. He left a proof using this technique for the case of n = 4 which I will go over in a future blog. He also wrote about its use in the proof for the case of n = 3 in a letter to Christian Huygens.

If Fermat had really found a proof for his theorem, it was without doubt based on this method.

To show the technique in action, I will use it to prove the following theorem:

Thereom: Relatively Prime Divisors of an n-power are themselves n-powers.

This theorem says that if gcd(v,w) = 1 and vw = zn
Then, there exists x,y such that v = xn, w = yn

(1) So, we start with gcd(v,w) = 1, vw = zn
(2) Assume that v is not equal to any number xn
(3) v ≠ 1 since 1 is an xn power
(4) Now, v is divisible by a prime number p. [Fundamental Theorem of Arithmetic]
(5) So, there exists k such that v = pk
(6) p divides z since zn = vw = pkw [By applying Euclid's Lemma]
(7) So, there exists m such that z=pm
(8) So, zn = vw = pkw = (pm)n = pnmn
(9) Dividing p from both sides gives us:
kw = p(n-1)mn
(10) From Euclid's Lemma, p divides k or w.
(11) It can't divide w since it already divides v and gcd(v,w)=1. Therefore, it divides k
(12) We can apply this same argument for each p in p(n-1)
(13) So, we can conclude that p(n-1) divides k.
(14) So, there exists V such that k = p(n-1)*V
(15) So, kw = p(n-1)mn = p(n-1)*V*w
(16) Dividing p(n-1) from both sides gives us:
Vw = mn
(17) Now, gcd(V,w)=1 since V is a divisor of v and gcd(v,w) = 1
(18) Likewise, V cannot be an n-power. If it were, then v = pnV would make v an n-power which goes against our assumption.
(19) Finally, V is less than v since p(n-1) > 1.
(20) Thus, we have a contradiction by infinite descent.

QED

We proved that assuming that a relatively prime divisor of an n-power is not itself an n-power means that there must necessarily be a smaller relatively prime divisor that is also not an n-power and so on and so on.

Here is what Fermat wrote about Infinite Descent in a letter to another mathematician:

"As ordinary methods, such as are found in books, are inadequate
to proving such difficult propositions, I discovered at last
a most singular method...which I called the infinite descent.
At first I used it to prove only negative assertions, such as
'There is no right angled triangle in numbers whose area is a
square'... To apply it to affirmative questions is much harder,
so when I had to prove 'Every prime of the form 4n+1 is a sum
of two squares" I found myself in a sorry plight (en belle
peine). But at last such questions proved amenable to my methods."
-Quoted from Andre Weil's Number Theory

4 comments:

Anonymous said...

just stumbled upon your blog...any ideas on this? http://www.manilatimes.net/national/2005/may/05/yehey/top_stories/20050505top4.html

Larry Freeman said...

Hi Drew,

Its a fake. Here are the details:
http://www.pcij.org/blog/?p=73

-Larry

Raimundo CL said...

Hi,

just to confirm that in line 16 of the proof instead of vW it is Vw. Only a detail.

Larry Freeman said...

Hi Raimundo,

Thanks for calling that out. I just fixed it.

Cheers,

-Larry