# Divisor Relation is Transitive

## 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$