Euclidean algorithm yields gcd and Bézout identity

Euclidean algorithm yields gcd and Bézout identity: Let $R$ be a Euclidean domain and let $a,b\in R$ be not both zero. The Euclidean algorithm produces $d\in R$ and $x,y\in R$ such that $d=\gcd(a,b)$ and $d=ax+by$. Equivalently, $(a,b)=(d)$ as ideals.

In a Euclidean domain , the algorithm computes a gcd and simultaneously shows that the ideal generated by $a$ and $b$ is a principal ideal . This is the core input for Euclidean implies PID .