Proof of $\gcd(a,b)=ax+by\ $ [Bezout's identity]

The nicest proof I know is as follows:

Consider the set $S = \{ax+by>0 : a,b \in \mathbb{Z}\}$. Let $d = \min S$. We now show the following:

• $d$ is a common divisor of $a$ and $b$.
• Any common divisor of $a$ and $b$ must divide $d$.

If we can show those two things then it is trivial that $d$ is the greatest common divisor of $a$ and $b$, and therefore that the greatest common divisor of $a$ and $b$ is of the form $ax+by$.

To show that $d$ divides $a$ and $b$: suppose for a contradiction that $d$ does not divide $a$. Then $a=qd+r$, where $q\ge 0$ and $0<r<d$. Since $a=qd+r$, $qd=a-r$, and since we have that $d=ax+by$, $q(ax+by)=a-r$, so $r=a(1-qx)-bqy$. So $r$ is a linear combination of $a$ and $b$, and since $r>0$, that means that $r\in S$. Since $r<d$ and we had supposed $d$ to be $\min S$, we have a contradiction. So $d$ must divide $a$.

An identical argument proves that $d$ must divide $b$.

We now want to show that any common divisor of $a$ and $b$ must divide $d$. This is easy to show: if $a=uc$ and $b=vc$, then $d=ax+by=c(ux+vy)$, so $c$ divides $d$.

Therefore, $d$ is the greatest common divisor of $a$ and $b$, and is of the form $ax+by$.

You ask: what is the easiest proof of the linear representation of the gcd? (Bezout's Identity). One candidate is the conceptual proof below - which highlights the implicit ideal structure - whose fundamental role will become clearer when one studies abstract algebra and number theory.

The set $\rm\,S\,$ of integers of form $\rm\,x\,a + y\,b,\ x,y\in \mathbb Z\,$ is closed under subtraction so, by the Lemma below, all $\rm\,n\in S\,$ are divisible by the least positive $\rm\,d\in S.\,$ Thus $\rm\,a,b\in S\,$ $\Rightarrow$ $\rm\,d\,|\,a,b,\,$ i.e. $\rm\,d\,$ is a common divisor of $\rm\,a,b,\,$ necessarily greatest, by $\rm\,c\,|\,a,b\,$ $\Rightarrow$ $\rm\,c\,|\,\color{#0a0}{d =\hat x\,a+\hat y\,b}\,$ $\Rightarrow$ $\rm\,c\le d,\,$ (i.e. common divisors representable in such $\rm\color{#0a0}{linear\ form}$ are always greatest).

Lemma $\ \ $ If a nonempty set of positive integers $\rm\: S\:$ satisfies $\rm\ n > m\ \in\ S \ \Rightarrow\ \: n-m\ \in\ S$
then every element of $\rm\:S\:$ is a multiple of the least element $\rm\:\ell \in S.$

Proof ${\bf\ 1}\,\ $ If not there is a least nonmultiple $\,n\in \rm S,\,$ contra $\rm\,n-\ell \in S\,$ is a nonmultiple of $\rm\,\ell.$

Proof ${\bf\ 2}\,\rm\,\ \ S\,$ closed under subtraction $\rm\,\Rightarrow\,S\,$ closed under remainder (mod), when it is $\ne 0,$ since mod is simply repeated subtraction, i.e. $\rm\ a\ mod\ b\, =\, a - k b\, =\, a\!-\!b\!-\!b\!-\cdots\! -\!b.\,$ Therefore $\rm\,n\in S\,$ $\Rightarrow$ $\rm\, (n\ mod\ \ell) = 0,\,$ else it is in $\,\rm S\,$ and smaller than $\rm\,\ell,\,$ contra minimality of $\rm\,\ell.$

Remark $\ $ In a nutshell, two applications of induction yield the following inferences

$$\begin{align} &\rm S\ \rm closed\ under\ {\bf subtraction}\\[.1em] \Rightarrow\ \ &\rm S\ closed\ under\ {\bf mod} = remainder = repeated\ subtraction \\[.1em] \Rightarrow\ \ &\rm S\ closed\ under\ {\bf gcd} = repeated\ mod\ (Euclidean\ algorithm) \end{align}\qquad\qquad$$

Interpreted constructively, this yields the extended Euclidean algorithm for the gcd. Namely, $ $ starting from the two elements of $\rm\,S\,$ that we know: $\rm\ a \,=\, 1\cdot a + 0\cdot b,\ \ b \,=\, 0\cdot a + 1\cdot b,\, $ we search for the least element of $\rm\,S\,$ by repeatedly subtracting elements of $\,\rm S\,$ to produce smaller elements of $\rm\,S\,$ (while keeping track of each elements linear representation in terms of $\rm\,a\,$ and $\rm\,b).\:$ This is essentially the subtractive form of the Euclidean GCD algorithm (vs. the mod / remainder form), where each reduction / descent step employs subtraction (vs. iterated subtraction = mod). In more general rings with a Euclidean division algorithm, e.g. polynomials over a field, we need to use proof $2$ to descend to a "smaller" element via mod (remainder), since mod is no longer calculable by repeated subtraction.

See also this answer for a direct inductive proof.

The conceptual structure will be clarified when one studies ideals of rings, where the above proof generalizes to show that Euclidean domains are PIDs.

Beware $ $ This $\rm\color{#0a0}{linear}$ representation of the the gcd need not hold true in all domains where gcds exist, e.g. in the domain $\rm\:D = \mathbb Q[x,y]\:$ of polynomials in $\rm\:x,y\:$ with rational coefficients we have $\rm\:gcd(x,y) = 1\:$ but there are no $\rm\:f(x,y),\: g(x,y)\in D\:$ such that $\rm\:x\:f(x,y) + y\:g(x,y) = 1;\:$ indeed, if so, then evaluating at $\rm\:x = 0 = y\:$ yields $\,0 = 1\,$ in $\rm D,\,$ contra $\rm D$ is a domain.