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?

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.
