Editing Proof by infinite descent (section)

{{Short description|Mathematical proof technique using contradiction}}
In [[mathematics]], a proof by '''infinite descent''', also known as Fermat's method of descent, is a particular kind of [[proof by contradiction]]<ref>{{Cite book |last=Benson |first=Donald C. |url=https://books.google.com/books?id=8_vbuzxrpfIC |title=The Moment of Proof: Mathematical Epiphanies |date=2000 |publisher=Oxford University Press |isbn=978-0-19-513919-8 |pages=43 |language=en |quote=a special case of proof by contradiction called the method of infinite descent}}</ref> used to show that a statement cannot possibly hold for any number, by showing that if the statement were to hold for a number, then the same would be true for a smaller number, leading to an infinite descent and ultimately a contradiction.<ref name=":0">{{Cite web|url=https://www.cut-the-knot.org/WhatIs/WhatIsInfiniteDescent.shtml|title=What Is Infinite Descent|website=www.cut-the-knot.org|access-date=2019-12-10}}</ref> It is a method which relies on the [[well-ordering principle]], and is often used to show that a given equation, such as a [[Diophantine equation]], has no solutions.<ref name=":1">{{Cite web|url=https://brilliant.org/wiki/general-diophantine-equations-fermats-method-of/|title=Fermat's Method of Infinite Descent {{!}} Brilliant Math & Science Wiki|website=brilliant.org|language=en-us|access-date=2019-12-10}}</ref><ref name=":2">{{Cite web|url=https://www.math.uci.edu/~ndonalds/math180b/5descent.pdf|title=Fermat's Method of Descent|last=Donaldson|first=Neil|website=math.uci.edu|access-date=2019-12-10}}</ref>

Typically, one shows that if a solution to a problem existed, which in some sense was related to one or more [[Natural number|natural numbers]], it would necessarily imply that a second solution existed, which was related to one or more 'smaller' natural numbers. This in turn would imply a third solution related to smaller natural numbers, implying a fourth solution, therefore a fifth solution, and so on. However, there cannot be an infinity of ever-smaller natural numbers, and therefore by [[mathematical induction]], the original premise&mdash;that any solution exists&mdash;is incorrect: its correctness produces a [[contradiction]].

An alternative way to express this is to assume one or more solutions or examples exists, from which a smallest solution or example&mdash;a [[minimal counterexample]]—can then be inferred. Once there, one would try to prove that if a smallest solution exists, then it must imply the existence of a smaller solution (in some sense), which again proves that the existence of any solution would lead to a contradiction.

The earliest uses of the method of infinite descent appear in [[Euclid's Elements|Euclid's ''Elements'']].<ref name=":1" /> A typical example is Proposition 31 of Book 7, in which [[Euclid]] proves that every composite integer is divided (in Euclid's terminology "measured") by some prime number.<ref name=":0" /> 

The method was much later developed by [[Fermat]], who coined the term and often used it for [[Diophantine equation]]s.<ref name=":2" /><ref>{{citation | last = Weil | first = André | author-link = André Weil | title = Number Theory: An approach through history from Hammurapi to Legendre | publisher = [[Birkhäuser Verlag|Birkhäuser]] | year = 1984 | pages = 75–79 | isbn = 0-8176-3141-0}}</ref> Two typical examples are showing the non-solvability of the Diophantine equation <math>r^2+s^4=t^4</math> and proving [[Fermat's theorem on sums of two squares]], which states that an odd prime ''p'' can be expressed as a sum of two [[square number|squares]] when <math>p\equiv1\pmod{4}</math> (see [[Modular arithmetic]] and [[Proofs of Fermat's theorem on sums of two squares#Euler.27s proof by infinite descent|proof by infinite descent]]). In this way Fermat was able to show the non-existence of solutions in many cases of Diophantine equations of classical interest (for example, the problem of four perfect squares in [[arithmetic progression]]).

In some cases, to the modern eye, his "method of infinite descent" is an exploitation of the [[Inversive geometry|inversion]] of the doubling function for [[rational point]]s on an [[elliptic curve]] ''E''. The context is of a hypothetical non-trivial rational point on ''E''. Doubling a point on ''E'' roughly doubles the length of the numbers required to write it (as number of digits), so that "halving" a point gives a rational with smaller terms. Since the terms are positive, they cannot decrease forever.