# Proof that substitution is allowed in the integers.

I'm taking an intro to proof via number theory class and I'm trying to prove that if a|b and b|c then a|c. So you write down there exist integers k and m such that ka = b and mb = c. Then you substitute ka in for b in the second equation and write (mk)a = c (by associative property). We know (mk) is an integer by the Closure property and so a|c. My question is, how do we know substitution is allowed (or is it not)? Is this something that can be proven from the Axioms of the Integers or something inherent in equivalence relations? Any insight would be awesome thank you!

• $k a =b$ means that $k a$ and $b$ are the same thing, so any assertion about $b$ is the same assertion when $k a$ is substituted for $b$ in that assertion. – DanielWainfleet Apr 5 '16 at 3:20

If $x=y$ then $nx=ny$.
It follows that $ka=b$ implies $m(ka)=mb$.
$$c=mb=m(ka)=(mk)a$$
• If you have an algebraic expression in terms of $n$, you can build it as a series of simple substitutions like the above. For example, if you know $n=5k$, and want to show $n^2 = 25k^2$ you can do this: $n = 5k$ implies $n(n) = n(5k)$. On the other hand, $n=5k$ implies $(5k)n=(5k)(5k)$. By transitivity, associativity, commutativity you conclude $n(n) = (5k)(5k)$. Couple this with the analogous addition substitution, and you can prove substitutions in any algebraic ("polynomial") expression are valid. – David Peterson Apr 5 '16 at 3:20