# Divisor Relation is Transitive/Proof 2

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

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