---
tag: SN89E2RKSA
kind: proof
name: Proof of Bézout's identity in a Euclidean domain
msc: [13F07]
proves: 0VY3WPP9Y3
uses: [0GJ2HRG95T, 0QKVE1GD9A, 0RZYDVZ475, 0MYSA6MYNA, 00A2EDFT9Q, 030TZ0DQWT, 0F7KNJ1ZYN, 04GNK7K4VP]
sources:
  - url: https://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity
    locator: For principal ideal domains
---

## Proof

Let $R$ be a [[Euclidean domain|0GJ2HRG95T]] and let $a, b \in R$.

1. Let $I = \set{s a + t b : s, t \in R}$. It contains $0 = 0 a + 0 b$, and also $a = 1 a + 0 b$ and $b = 0 a + 1 b$.
2. For $s a + t b$ and $s' a + t' b$ in $I$ and $r \in R$, we have $(s a + t b) - (s' a + t' b) = (s - s') a + (t - t') b \in I$ and $r (s a + t b) = (r s) a + (r t) b \in I$.
3. By steps 1 and 2, $I$ is an [[ideal|0MYSA6MYNA]] of $R$.
4. Since [[Euclidean domains are principal ideal domains|0QKVE1GD9A]], $I$ is a [[principal ideal|00A2EDFT9Q]]: $I = (d)$ for some $d \in R$.
5. The set $d R = \set{d r : r \in R}$ is an ideal that contains $d$. Every ideal containing $d$ contains $d R$. So the [[ideal generated by|030TZ0DQWT]] $d$ is $(d) = d R$.
6. Since $d \in (d) = I$, there are $s, t \in R$ with $d = s a + t b$.
7. Since $a \in I = d R$, $d$ [[divides|04GNK7K4VP]] $a$. In the same way, $d \mid b$.
8. Let $c \in R$ with $c \mid a$ and $c \mid b$, say $a = c a_1$ and $b = c b_1$. Then $d = s c a_1 + t c b_1 = c (s a_1 + t b_1)$, so $c \mid d$.
9. By steps 7 and 8, $d$ is a [[greatest common divisor|0F7KNJ1ZYN]] of $a$ and $b$. By step 6, $d = s a + t b$.

## Idea

The combinations $s a + t b$ form an ideal. In a Euclidean domain every ideal is generated by one element $d$. This $d$ is itself a combination of $a$ and $b$, it divides both, and every common divisor of $a$ and $b$ divides every combination of them, hence divides $d$.