# Proof (Divisibility): If a|b and b|c then a|c

Ok, here is what I have for the proof of this conjecture. Let me know if I'm on the right path? all input appreciated.

There exist integers $j$, $k$, and $m$, such that, $b = aj$ and $c = ajk.$ Then $c = ajk$ (substituting $aj$ for $b$) let $m = jk$, then $c = ma, => a|c.$

-
Upvoted for showing work, though I feel like I've seen this question 3x on this site! –  The Chaz 2.0 Nov 12 '12 at 4:43

Yes, $b=aj$ and $c=bk=ajk=(jk)a$. Since $jk \in \mathbb{Z}$, we have $a|c$.

-

Note that,

$$a|b \implies b=ma \,,$$

and

$$b|c \implies c =nb \implies c = nma \implies c = q a \implies a|c \,,$$

for $m,n,q \in \mathbb{Z}$ and $q=nm.$

-

(In this answer all variables are integers, i.e., elements of $\mathbb{Z}$.)

By the definition of divisibility we are given that $\;n * a = b\;$ and $\;m * b = c\;$ for some $\;n\;$ and $\;m\;$. Now we are asked to find a $\;k\;$ which makes $\;k*a = c\;$:

\begin{align} & k*a = c \\ \equiv & \;\;\;\;\;\text{"use the only fact we know about $\;c\;$"} \\ & k*a = m*b \\ \equiv & \;\;\;\;\;\text{"use the other fact"} \\ & k*a = m*n*a \\ \Leftarrow & \;\;\;\;\;\text{"weaken using Leibniz' rule -- to achieve our goal"} \\ & k = m*n \\ \end{align}

Therefore we have found such a $\;k\;$, and hence proved $\;a|c\;$.

-