Below is a simple conceptual proof of Bezout's identity for the gcd.
The set $\rm\:S\:$ of all integers of form $\rm\:a\:x + b\:y,\,\ x,y\in \mathbb Z,\:$ is closed under subtraction so, by Lemma below, every positive $\rm\:n\in S\:$ is divisible by $\rm\:d = $ least positive $\rm\in S,\:$ so $\rm\:a,b\in S\:$ $\Rightarrow$ $\rm\:d\:|\:a,b.\:$ Thus $\rm\:d\:$ is a common divisor of $\rm\:a,b,\:$ necessarily greatest, $ $ by $\rm\:c\:|\:a,b\:$ $\Rightarrow$ $\rm\:c\:|\:d = a\:x\!+\! b\:y\:$ $\Rightarrow$ $\rm\:c\le d.$
Lemma $\ $ If a nonempty set of positive integers $\rm\: S\:$ satisfies both $\rm\ n > m\: \in\, S \ \Rightarrow\ n-m\, \in\, S$
then every element of $\rm\:S\:$ is a multiple of the least element $\rm\:m_{\circ} \in\, S.$
Proof $\,\bf 1$ $\ $ If not there is a least nonmultiple $\rm\:n\in S,\,$ contra $\rm\:n-m_{\circ} \in S\:$ is a nonmultiple of $\rm\:m_{\circ}$
Proof $\,\bf 2$ $\rm\ \ S\,$ closed under subtraction $\rm\:\Rightarrow\:S\,$ closed under remainder (mod), when it is $\ne 0,$ since mod may be computed by repeated subtraction, i.e. $\rm\: a\ mod\ b\, =\, a - k b\, =\, a-b-b-\cdots -b.\:$ Hence $\rm\:n\in S\:$ $\Rightarrow$ $\rm\: n\ mod\ m_\circ = 0,\:$ else it is $\rm\,\in S\,$ and smaller than $\rm\:m_\circ\,$ contra mimimality of $\rm\:m_\circ$
Remark $\ $ In a nutshell, two applications of induction yield the following inferences
$$\!\rm\begin{eqnarray} S\ closed\ under\ subtraction &\!\Rightarrow\:&\rm S\ closed\ under\ mod \!=\! remainder = repeated\ subtraction \\
&\!\Rightarrow\:&\rm S\ closed\ under\ gcd\! =\! repeated\ remainder\!\!: Euclid'\!s\ algorithm \end{eqnarray}$$
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 to produce smaller elements of $\rm\,S\,$ (while keeping track of every elements linear representation in terms of $\rm\,a\,$ and $\rm\,b).\:$ This is essentially the subtractive form of the Euclidean algorithm (vs. the mod/remainder form).
Best Answer
Euclid's Division Lemma states: for $a$, $b\in\mathbb{Z}$, $b\ne0$, there exist unique $q$, $r\in\mathbb{Z}$ such that $$a=qb+r, \qquad 0\le r<|b|\tag{$\star$}$$
We call $q$ the quotient, and $r$ the remainder. The lemma itself can be proved by induction on $a$. Euclid's Division Algorithm is an algorithm to find the greatest common divisor ($\gcd$) of two natural numbers facilitated by repeated use of the Division Lemma until in the last use of $(\star)$ we get a zero remainder and the process terminates with the $\gcd$ given by the last non-zero remainder. Each time the Division Lemma is invoked in the Division Algorithm, the new $a$ and $b$ are the preceding steps $b$ and $r$ respectively.
For example to find $\gcd(267,126)$ the Division Algorithm takes four steps to get to a zero-remainder, each step a usage of the Division Lemma:
Step 1: Find the remainder when $267$ is divided by $126$. By Euclid's Division Lemma with $a_1=267$, $b_1=126$, we have $$267=2\times126+15\tag{1}$$ and so $q_1=2$, $r_1=15$.
Step 2: Find the remainder when $126$ is divided by $15$. By Euclid's Division Lemma with $a_2=126$, $b_2=15$, we have $$126=8\times15+6\tag{2}$$ and so $q_2=8$, and $r_2=6$.
Step 3: Find the remainder when $15$ is divided by $6$. By Euclid's Division Lemma with $a_3=15$, $b_3=6$, we have $$15=2\times6+3\tag{3}$$ and so $q_3=2$, $r_3=3$.
Step 4: Find the remainder when $6$ is divided by $3$. By Euclid's Division Lemma with $a_4=6$, $b_4=3$, we have $$6=2\times3+0\tag{4}$$ and so $q_4=2$, $r_4=0$. Here the Division Algorithm terminates since $r_4=0$, and $\gcd(267,126)=r_3=3$ is the last non-zero remainder from Step 3.