Proof that a|b ∧ b|c .→. a|c

Show that if a|b and b|c, then a|c.

To prove: If $a \mid b$ and $b \mid c$, then $a \mid c$.

---

Definitions:

• $a \mid b$ means there exists an integer $k$ such that $b = ak$.
• $b \mid c$ means there exists an integer $m$ such that $c = bm$.

---

Proof:

Given:

• $b = ak$ for some $k \in \mathbb{Z}$ (since $a \mid b$)
• $c = bm$ for some $m \in \mathbb{Z}$ (since $b \mid c$)

Substitute $b = ak$ into the equation for $c$:

$$ c = bm = (ak)m = a(km) $$

Since $km \in \mathbb{Z}$ (product of integers is an integer), we have:

$$ c = a(km) \Rightarrow a \mid c $$

---

Conclusion:

We have shown that $c$ is a multiple of $a$, so $a \mid c$. Thus, if $a \mid b$ and $b \mid c$, then $a \mid c$. □