Canonical: https://knowlpedia.com/algebra-rings/euclidean-algorithm/

# Euclidean algorithm yields gcd and Bézout identity

In a Euclidean domain, the Euclidean algorithm computes a gcd and expresses it as a linear combination.

**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.

## Remarks

In a [Euclidean domain](https://knowlpedia.com/algebra-rings/euclidean-domain/), the algorithm computes a [gcd](https://knowlpedia.com/algebra-rings/gcd/) and simultaneously shows that the ideal [generated](https://knowlpedia.com/algebra-rings/ideal-generated/) by \(a\) and \(b\) is a [principal ideal](https://knowlpedia.com/algebra-rings/principal-ideal/). This is the core input for [Euclidean implies PID](https://knowlpedia.com/algebra-rings/euclidean-implies-pid/).
