What is an example of a proof by minimal counterexample? I was reading about proof by infinite descent, and proof by minimal counterexample. My understanding of it is that we assume the existance of some smallest counterexample $A$ that disproves some proposition $P$, then go onto show that there is some smaller counterexample to this which to me seems like a mix of infinite descent and 'reverse proof by contradiction'. 
My question is, how do we know that there might be some counterexample? Furthermore, are there any examples of this?
 A: Consider, for instance, the statement

Every $n\in\mathbb{N}\setminus\{1\}$ can be written as a product of prime numbers (including the case in which there's a single prime number appearing only once).

Suppose otherwise. Then there would be a smallest $n\in\mathbb{N}\setminus\{1\}$ that could not be expressed as a product of prime numbers. In particular, this implies that $n$ cannot be a prime number. Since $n$ is also different from $1$, it can be written as $a\times b$, where $a,b\in\{2,3,\ldots,n-1\}$. Since $n$ is the smallest counterexample, neither $a$ nor $b$ are counterexamples and therefore both of them can be written as a product of prime numbers. But then $n(=a\times b)$ can be written in such a way too.
A: Such a proof will often go as follows.


*

*Assume for contradiction that there is a counterexample to $P$ within some well-ordered set $X$.

*Consider the (certainly non-empty) set of all $X$ which are counterexamples to $P$. This set has a least element (that's what it means to be a well-order), so…

*Consider the smallest counterexample.

*Show that you can find a smaller counterexample.

*Contradiction, so there can't have been any counterexamples to $P$ after all.

*Therefore $P$ is true.

A: Assume the $\sqrt{2}$ is rational. Then there are whole numbers $a$ and $b$ such that $\sqrt{2}=a/b$ and $a$ is the smallest number with this property but then we find that $a/2, b/2$ are also whole numbers with this property. So there is a smaller example. 
I think this must be the example people are the most familiar with and it's a kind of infinite descent even though we often don't refer to it as such. 
A: Fundamental examples in number theory  arise via  descent by (Euclidean) division with remainder (or, equivalently in $\Bbb Z$, by repeated subtraction), as in the following basic  result.
Lemma $\  $ Let $\,S\,$ be a nonempty set of positive integers that is closed under subtraction $> 0,\,$ i.e. for all $ \,n,m\in S, \,$ $ \ n > m\ \Rightarrow\  n-m\, \in\, S.\,$  Then the $\rm\color{#c00}{least}$ $ \:\ell\in S\,$ divides every element of $\,  S.$
Proof ${\bf\ 1}\,\  $ If not there is a $\rm\color{#c00}{least}$  nonmultiple $\,n\in S,\,$ contra  $\,n-\ell \in S\,$ is a nonmultiple of $ \,\ell.$
Proof ${\bf\ 2}\,\ \   S\,$ closed under subtraction $ \,\Rightarrow\,S\,$ closed under remainder (mod), when it is $\ne 0,$ because mod is simply repeated subtraction, i.e. $ \ a\bmod\ b\, =\, a - k b\, =\, a\!-\!b\!-\!b\!-\cdots\! -\!b.\ $ Hence $ \,n\in S\,$ $\Rightarrow$ $ \, (n\bmod \ell) = 0,\,$ else it's in $S$ and smaller than $ \,\ell,\,$ contra $\rm\color{#c00}{minimality}$ of $ \,\ell.$
Remark $\ $ In a nutshell, two applications of induction yield the following inferences
$\begin{eqnarray}\rm S\ closed\ under\ {\bf subtraction} &\:\Rightarrow\:&\rm S\ closed\ under\ {\bf mod} = remainder = repeated\ subtraction \\
&\:\Rightarrow\:&\rm S\ closed\ under\ {\bf gcd} = repeated\ mod\ (Euclid's\ algorithm) \end{eqnarray}$
This yields Bezout's GCD identity: the set $ \,S\,$ of integers of form $ \,a_1\,x_1 + \cdots + a_n x_n,\ x_i\in \mathbb Z,\,$ is closed under subtraction so Lemma $\Rightarrow$  every positive $ \,k\in S\,$ is divisible by $ \,d = $ least positive $ \in S.\,$  Therefore $ \,a_i\in S$ $\,\Rightarrow\,$ $  d\mid a_i,\,$ i.e. $ \,d\,$ is a common divisor of all $ \,a_i,\,$ necessarily the greatest such because $ \ c\mid a_i$ $\Rightarrow$ $ \,c\mid d = a_!\,x_1\!+\!\cdots\!+\!a_nx_n$ $\Rightarrow$ $ \,c\le d.\,$   When interpreted constructively, this yields the extended Euclidean algorithm for the gcd.
