Existence of a Bézout identity

Well-ordering. $S$ is a nonempty set of positive integers (for example, $a^2+b^2\in S$). Let $d'$ be its smallest element, written $d'=au+bv$.

Division. Divide $a$ by $d'$: $a=d'q+r$ with $0\le r<d'$. Then
$$r=a-d'q=a-(au+bv)q=a(1-uq)+b(-vq).$$
So $r$ is a linear combination of $a$ and $b$. If $r>0$, then $r\in S$ and $r<d'$, contradicting the minimality of $d'$. Hence $r=0$, so $d'\mid a$. Similarly $d'\mid b$.

Conclusion. $d'$ is a common divisor of $a$ and $b$, so $d'\le d$. On the other hand, $d$ divides every linear combination of $a$ and $b$, so $d\mid d'$, hence $d\le d'$. Therefore $d'=d$, and $d$ has a Bézout representation.