Euclid's Lemma for Euclidean Domains

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\struct {D, +, \times}$ be a Euclidean domain whose unity is $1$.

Let $a, b, c \in D$.

Let $a \divides b \times c$, where $\divides$ denotes divisibility.


Let $a \perp b$, where $\perp$ denotes relative primeness.

Then $a \divides c$.


Proof

\(\ds a\) \(\perp\) \(\ds b\)
\(\ds \leadsto \ \ \) \(\ds \gcd \set {a, b}\) \(=\) \(\ds 1\) Definition of Coprime Elements of Euclidean Domain
\(\ds \leadsto \ \ \) \(\, \ds \exists x, y \in D: \, \) \(\ds a \times x + b \times y\) \(=\) \(\ds 1\) Bézout's Lemma on Euclidean Domain
\(\ds \leadsto \ \ \) \(\ds c\) \(=\) \(\ds c \times \paren {a \times x + b \times y}\)
\(\ds \) \(=\) \(\ds c \times a \times x + c \times b \times y\)
\(\ds \) \(=\) \(\ds \paren {a \times c} \times x + \paren {b \times c} \times y\)
\(\ds \leadsto \ \ \) \(\ds a\) \(\divides\) \(\ds c \times \paren {a \times x + b \times y}\) as $a \divides a \times c$ and $a \divides b \times c$
\(\ds \) \(=\) \(\ds c \times 1\) Bézout's Lemma on Euclidean Domain
\(\ds \) \(=\) \(\ds c\)

$\blacksquare$


Source of Name

This entry was named for Euclid.


Also see

  • Euclid's Lemma, for the usual statement of this result, which is this lemma as applied specifically to the integers.


Sources