Every nonempty subset of the natural numbers has a least element in their usual order. Applying this principle to positive integer linear combinations proves Bézout's identity. This principle for the usual natural-number order is distinct from the general well-ordering theorem asserting that every set can be equipped with some well-order.
Assume that a proposed statement fails for some natural number, and choose the least failing index using the well-ordering principle. Prove the necessary base cases and reduce the least failure to a smaller index that must satisfy the statement. If that smaller case implies the alleged failure also satisfies it, there is a contradiction. Reductions by a step larger than one require enough consecutive base cases to cover every possible residue class.

Articles by others on the same topic (0)

There are currently no matching articles.