Bézout's identity

Consider the set $S=\{au+bv : u,v\in\mathbb{Z}\}\cap\mathbb{Z}_{>0}$ of all strictly positive integer combinations of $a$ and $b$. Since $a,b$ are not both $0$, $S$ is nonempty (it contains $|a|$ or $|b|$), so by the well-ordering principle $S$ has a least element $d=au_0+bv_0>0$.

We show $d\mid a$: divide $a=qd+r$ with $0\le r<d$. Then $r=a-qd=a-q(au_0+bv_0)=a(1-qu_0)+b(-qv_0)$ is itself an integer combination of $a,b$. If $r>0$ then $r$ would belong to $S$ and be smaller than $d$, contradicting minimality; so $r=0$, i.e. $d\mid a$. The identical argument with $b$ in place of $a$ shows $d\mid b$.

Since $d$ is a common divisor of $a$ and $b$, $d\le \gcd(a,b)$. Conversely, any common divisor $e$ of $a$ and $b$ divides $au_0+bv_0=d$, so $e\le d$; taking $e=\gcd(a,b)$ gives $\gcd(a,b)\le d$.

Combining both inequalities, $d=\gcd(a,b)$, and by construction $d=au_0+bv_0$, which is exactly Bézout's identity with $u=u_0,v=v_0$.