Divides is Transitive

From ProofWiki

Jump to: navigation, search

Theorem

Let $\left({D, +, \circ}\right)$ be an integral domain.

Let $x, y, z \in D$.

Then:

$x \backslash y \land y \backslash z \implies x \backslash z$

Let $x \backslash y \land y \backslash z$.

Then from the definition of divisor, we have:

Then:

$z = t \circ \left({s \circ x}\right) = \left({t \circ s}\right) \circ x$

Thus:

$\exists \left({t \circ s}\right) \in D: z = \left({t \circ s}\right) \circ x$

and the result follows.

$\blacksquare$

Follows directly from the fact that Integers form Integral Domain.

$\blacksquare$

Alternatively:

$\forall x, y, z \in \Z: x \backslash y \land y \backslash z \implies x \backslash z$

This follows because:

$\displaystyle $	$\displaystyle $	$\displaystyle $	$\displaystyle x \backslash y$	$\implies$	$\displaystyle \exists q_1 \in \Z: q_1 x = y$	$\displaystyle $	$\displaystyle $	$\displaystyle $
$\displaystyle $	$\displaystyle $	$\displaystyle $	$\displaystyle y \backslash z$	$\implies$	$\displaystyle \exists q_2 \in \Z: q_2 y = z$	$\displaystyle $	$\displaystyle $	$\displaystyle $
$\displaystyle $	$\displaystyle \implies$	$\displaystyle $	$\displaystyle q_2 \left({q_1 x}\right)$	$=$	$\displaystyle z$	$\displaystyle $	$\displaystyle $	$\displaystyle $
$\displaystyle $	$\displaystyle \implies$	$\displaystyle $	$\displaystyle \left({q_2 q_1 x}\right)$	$=$	$\displaystyle z$	$\displaystyle $	$\displaystyle $	$\displaystyle $
$\displaystyle $	$\displaystyle \implies$	$\displaystyle $	$\displaystyle q \in \Z: q x$	$=$	$\displaystyle z$	$\displaystyle $	$\displaystyle $	$\displaystyle $
$\displaystyle $	$\displaystyle \implies$	$\displaystyle $	$\displaystyle x \backslash z$		$\displaystyle $	$\displaystyle $	$\displaystyle $	$\displaystyle $

$\blacksquare$

\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle x \backslash y\)	\(\implies\)	\(\displaystyle \exists q_1 \in \Z: q_1 x = y\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle y \backslash z\)	\(\implies\)	\(\displaystyle \exists q_2 \in \Z: q_2 y = z\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
\(\displaystyle \)	\(\displaystyle \implies\)	\(\displaystyle \)	\(\displaystyle q_2 \left({q_1 x}\right)\)	\(=\)	\(\displaystyle z\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
\(\displaystyle \)	\(\displaystyle \implies\)	\(\displaystyle \)	\(\displaystyle \left({q_2 q_1 x}\right)\)	\(=\)	\(\displaystyle z\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
\(\displaystyle \)	\(\displaystyle \implies\)	\(\displaystyle \)	\(\displaystyle q \in \Z: q x\)	\(=\)	\(\displaystyle z\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
\(\displaystyle \)	\(\displaystyle \implies\)	\(\displaystyle \)	\(\displaystyle x \backslash z\)	\(\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)