Euclid's Lemma

From ProofWiki

Jump to: navigation, search

This article was Proof of the Week between 29 December 2008 and 19 January 2009.

Theorem

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

If $a \backslash b c$, where $a$ and $b$ are relatively prime, then $a \backslash c$.

$\blacksquare$

Alternatively we can prove this result directly, without needing to refer to results from abstract algebra.

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

$a \perp b$ from the definition of relatively prime.

That is, $\gcd \left\{{a, b}\right\} = 1$.

From Common Divisor Divides Integer Combination, we may write $a x + b y = 1$ for some $x, y \in \Z$.

Upon multiplication by $c$, we see that $c = c \left({a x + b y}\right) = c a x + c b y$.

Since $a \backslash a c$ and $a \backslash b c$, it is clear that $a \backslash \left({c a x + c b y}\right)$.

However, $c a x + c b y = c \left({a x + b y}\right) = c \cdot 1 = c$.

Therefore, $a \backslash c$.

$\blacksquare$

This entry was named for Euclid.