Divisor Relation is Transitive

From ProofWiki
Jump to navigation Jump to search

Theorem

The divisibility relation is a transitive relation on $\Z$, the set of integers.

That is:

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


Proof 1

We have that Integers form Integral Domain.

The result then follows directly from Divisor Relation in Integral Domain is Transitive.

$\blacksquare$


Proof 2

\(\ds x\) \(\divides\) \(\ds y\)
\(\ds \leadsto \ \ \) \(\, \ds \exists q_1 \in \Z: \, \) \(\ds q_1 x\) \(=\) \(\ds y\) Definition of Divisor of Integer
\(\ds y\) \(\divides\) \(\ds z\)
\(\ds \leadsto \ \ \) \(\, \ds \exists q_2 \in \Z: \, \) \(\ds q_2 y\) \(=\) \(\ds z\) Definition of Divisor of Integer
\(\ds \leadsto \ \ \) \(\ds q_2 \paren {q_1 x}\) \(=\) \(\ds z\) substituting for $y$
\(\ds \leadsto \ \ \) \(\ds \paren {q_2 q_1} x\) \(=\) \(\ds z\) Integer Multiplication is Associative
\(\ds \leadsto \ \ \) \(\, \ds \exists q \in \Z: \, \) \(\ds q x\) \(=\) \(\ds z\) where $q = q_1 q_2$
\(\ds \leadsto \ \ \) \(\ds x\) \(\divides\) \(\ds z\) Definition of Divisor of Integer

$\blacksquare$


Sources