Euclidean Algorithm: A Review
Bézout’s Identity through the Lens of Algebra
Let $a, b$ be 2 positive integers, and denote by $d$ their greatest common divisor, then there exist 2 integers $s,t\in\mathbb{Z}$ such that $as+bt=d$.
Every subgroup $H$ of $(\mathbb{Z}, +)$ is of the form $n\mathbb{Z}$ for some $n \geq 0$.
We can see $a\mathbb{Z}+b\mathbb{Z}=\left\lbrace as+bt:s,t\in \mathbb{Z}\right\rbrace$ is a subgroup generated by $a$ and $b$, thus there exists a positive integer $d$ such that $a\mathbb{Z}+b\mathbb{Z}=d\mathbb{Z}$. This implies that there exist $s,t\in\mathbb{Z}$ such that $as+bt=d$. Moreover, since $a\in a\mathbb{Z}+b\mathbb{Z}=d\mathbb{Z}$, $d\mid a$. Similarly, $d\mid b$, which means $d$ is a common divisor of $a$ and $b$.
We next show that $d=\gcd(a,b)$. Indeed, if an integer $e$ divides both $a$ and $b$, then it also divides every linear combination $as+bt$, and in particular $d$. Thus $e \mid d$, $e\leq d$, showing that $d$ is the greatest common divisor.
We next show that $d=\gcd(a,b)$. Indeed, if an integer $e$ divides both $a$ and $b$, then it also divides every linear combination $as+bt$, and in particular $d$. Thus $e \mid d$, $e\leq d$, showing that $d$ is the greatest common divisor.
From the above proof, we can also see that for any positive integer $e$, if $e\mid a$ and $e\mid b$, then $e\mid \gcd(a,b)$.