---
tag: 023VY493K0
kind: concept
name: Euclidean algorithm in a Euclidean domain
msc: [13F07]
uses: [0GJ2HRG95T, 0F7KNJ1ZYN]
sources:
  - url: https://en.wikipedia.org/wiki/Euclidean_algorithm
    locator: Euclidean domains
---

## Summary

Let $R$ be a [[Euclidean domain|0GJ2HRG95T]] with Euclidean function $\delta$ and let $a, b \in R$.
The Euclidean algorithm sets $r_0 = a$ and $r_1 = b$. While $r_k \neq 0$, it divides $r_{k-1}$ by $r_k$ and lets $r_{k+1}$ be the remainder.
The values $\delta(r_k)$ decrease strictly, so the algorithm stops with some $r_{n+1} = 0$.
The last nonzero remainder $r_n$ is a [[greatest common divisor|0F7KNJ1ZYN]] of $a$ and $b$, if $b \neq 0$.

## Remarks

The algorithm works because the common divisors of $r_{k-1}$ and $r_k$ are the common divisors of $r_k$ and $r_{k+1}$.
In $\mathbb{Z}$: $252 = 1 \cdot 198 + 54$, $198 = 3 \cdot 54 + 36$, $54 = 1 \cdot 36 + 18$, $36 = 2 \cdot 18$. So $\gcd(252, 198) = 18$.
The extended algorithm also gives the coefficients of [[Bézout's identity|0VY3WPP9Y3]].

## Explanations

### L1 human

To find the gcd of two numbers, replace the larger one by its remainder modulo the smaller one, and repeat.
When the remainder is zero, the last divisor is the gcd.
The same steps work in every Euclidean domain, for example for polynomials over a field.