Divisor Relation is Transitive/Proof 2
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
\(\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
- 1969: C.R.J. Clapham: Introduction to Abstract Algebra ... (previous) ... (next): Chapter $3$: The Integers: $\S 10$. Divisibility: Theorem $16 \ \text{(i)}$