Proof of Bézout's identity

Proof

We show that the least positive integer of the form $ax + by$ is the greatest common divisor.

1. Let $a$ and $b$ be integers and let $d = \gcd(a, b)$.
2. If $a = b = 0$, then $d = 0$ by convention, and $x = y = 0$ give $a x + b y = 0 = d$. From now on, $a$ and $b$ are not both $0$.
3. Then $1$ is a common divisor, so $d \ge 1$.
4. Let $S$ be the set of positive integers of the form $a x + b y$ with $x, y \in \Z$. It contains $a \cdot a + b \cdot b = a^2 + b^2 > 0$, so $S$ is nonempty.
5. By the well-ordering principle, $S$ has a least element $e$. Write $e = a x_0 + b y_0$ with $x_0, y_0 \in \Z$.
6. By the division algorithm, $a = e q + r$ with integers $q$, $r$ and $0 \le r < e$.
7. Then $r = a - q(a x_0 + b y_0) = a(1 - q x_0) + b(-q y_0)$, so $r$ has the form $ax + by$.
8. If $r > 0$, then $r \in S$ and $r < e$, which contradicts the choice of $e$. So $r = 0$, and $e$ divides $a$.
9. The same argument with $b$ in place of $a$ shows that $e \mid b$. So $e$ is a common divisor, and $e \le d$ because $d$ is the largest one.
10. Since $d \mid a$ and $d \mid b$, write $a = d a'$ and $b = d b'$ with integers $a'$, $b'$. Then $e = d(a' x_0 + b' y_0)$.
11. Here $e > 0$ and $d > 0$, so the integer $a' x_0 + b' y_0$ is positive. Hence it is at least $1$, and $e \ge d$.
12. By steps 9 and 11, $e = d$. So $a x_0 + b y_0 = d$, and $x = x_0$, $y = y_0$ are the required integers.