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

Using axioms, you can prove

If $x=y$ then $nx=ny$.

It follows that $ka=b$ implies $m(ka)=mb$.

By properties of equality and associativity of multiplication we have

$$c=mb=m(ka)=(mk)a$$

• So is every instance of substitution really just a fancy consequence of this or is this just another way to accomplish the task without substitution? – Sean Haight Apr 5 '16 at 3:13
• 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