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). In my opinion it is the proof below, which also has much to offer conceptually, since it better highlights the implicit ideal structure. This fundamental algebraic structure will come to the fore in later studies.

The set $\rm\:S\:$ of integers of the form $\rm\:x\:a + y\:b,\ x,y\in \mathbb Z\:$ is closed under subtraction so, by the Lemma below, every $\rm\:n\in S\:$ is 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\:|\:d =\hat x\:a+\hat y\:b\:$ $\Rightarrow$ $\rm\:c\le d,\,$ (which shows that common divisors representable in such 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).

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 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.$