Bézout's Lemma/Proof 4

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $a, b \in \Z$ such that $a$ and $b$ are not both zero.


Let $\gcd \set {a, b}$ be the greatest common divisor of $a$ and $b$.

Then:

$\exists x, y \in \Z: a x + b y = \gcd \set {a, b}$


That is, $\gcd \set {a, b}$ is an integer combination (or linear combination) of $a$ and $b$.


Furthermore, $\gcd \set {a, b}$ is the smallest positive integer combination of $a$ and $b$.


Proof

Let $a, b \in \Z$ such that $a$ and $b$ are not both zero.

Let $J$ be the set of all integer combinations of $a$ and $b$:

$J = \set {x: x = m a + n b: m, n \in \Z}$


First we show that $J$ is an ideal of $\Z$

Let $\alpha = m_1 a + n_1 b$ and $\beta = m_2 a + n_2 b$, and let $c \in \Z$

Then $\alpha,\beta \in J$ and :


\(\ds \alpha + \beta\) \(=\) \(\ds m_1 a + n_1 b + m_2 a + n_2 b\)
\(\ds \) \(=\) \(\ds \paren {m_1 + m_2} a + \paren {n_1 + n_2} b\)
\(\ds \leadsto \ \ \) \(\ds \alpha + \beta\) \(\in\) \(\ds J\)


\(\ds c \alpha\) \(=\) \(\ds c \paren {m_1 a + n_1 b}\)
\(\ds \) \(=\) \(\ds \paren {c m_1} a + \paren {c n_1} b\)
\(\ds \leadsto \ \ \) \(\ds c \alpha\) \(\in\) \(\ds J\)


Thus $J$ is an integral ideal.

We have that:

\(\ds a\) \(=\) \(\ds 1 a + 0 b\)
\(\, \ds \land \, \) \(\ds b\) \(=\) \(\ds 0 a + 1 b\)
\(\ds \leadsto \ \ \) \(\ds a, b\) \(\in\) \(\ds J\)


$a$ and $b$ are not both zero, thus:

$J \ne \set 0$

By the something {theorem about ideals}:

$\exists x_0 > 0 : J = x_0 \Z$


$a \in J \land \set {J = x_0 \Z} \implies x_0 \divides a$
$b \in J \land \set {J = x_0 \Z} \implies x_0 \divides b$


$x_0 \divides a \land x_0 \divides b \implies x_0 \in \map D {a, b}$




Furthermore:

$x_0 \in J \implies \exists r, s \in \Z : x_0 = r a + s b$


Let $x_1 \in \map D {a, b}$.

Then:

\(\ds x_1 \in \map D {a, b}\) \(\leadsto\) \(\ds x_1 \divides a \land x_1 \divides b\)
\(\ds \) \(\leadsto\) \(\ds x_1 \divides \paren {r a + s b}\)
\(\ds \) \(\leadsto\) \(\ds x_1 \vert x_0\)
\(\ds \) \(\leadsto\) \(\ds \size {x_1} \le \size {x_0} = x_0\)

Thus:

$x_0 = \max \set {\map D {a, b} } = \gcd \set {a, b} = r a + s b$

$\blacksquare$