# If $d$ is a common divisor of $m$ and $n$, then so it is of $n$ and $m-n$

I am having trouble proving the following statement:

Prove that for all integers $m$ and $n$, if $d$ is a common divisor of $m$ and $n$ (but $d$ is not necessarily the GCD) then $d$ is a common divisor of $n$ and $m - n$.

I've noticed that for any integers $m,n,d$ that $m - n = kd$ (where $k$ is an integer as well). Any help or hints on how to prove this statement would be greatly appreciated.

• I don't think you have noticed what you say you noticed. Let $m=2,n=1$ and $d=3.$ Then we certainly cannot say that $m-n=kd$ for some integer $k.$ I think what you mean is that if $m,n,d$ are integers such that $d$ is a common divisor of $m,n$, then $m-n=kd$ for some integer $k.$ – Cameron Buie Nov 18 '13 at 20:08

For integers $d,m$, we say that $d$ divides $m$ if $\frac md$ is an integer. That is to say, $m = m'd$ for some integer $m' = \frac md$.

So we know that $m = m'd, n = n'd$. Hence $m-n = \ldots$

• $m - n = d(m' - n')$ which means it is divisible by $d$! Thank you! – wonggr Nov 18 '13 at 20:07

If $d$ divides $m$, then $m=m_1d$ for some integer $m_1$. Similarly, if $d$ divides $n$, then $n=n_1d$ for some integer $n_1$. And hence $$m-n=d(m_1-n_1).$$

• Thank you so much for the very concise explanation. – wonggr Nov 18 '13 at 20:09

Here is an answer that is a bit more formal than the others. "$\;d\;$ divides $\;n\;$", often written as $\;d | n\;$, is defined like this: $$(0) \;\;\; d | n \;\equiv\; \langle \exists q \in \mathbb Z :: q \cdot d = n \rangle$$

You are asked to prove $$d | m \:\land\: d | n \;\Rightarrow\; d | n \:\land\: d | (m-n)$$ for all $\;d,n,m\;$, or logically equivalently $$(1) \;\;\; d | m \:\land\: d | n \;\Rightarrow\; d | (m-n)$$

Starting with the consequent --since that is the most complex part-- we calculate as follows: \begin{align} & d | (m-n) \\ \equiv & \;\;\;\;\;\text{"definition $(0)$"} \\ & \langle \exists q \in \mathbb Z :: q \cdot d = m - n \rangle \\ \equiv & \;\;\;\;\;\text{"use assumptions $\;d | m\;$ and $\;d | n\;$ with $(0)$ to choose $\;q_1,q_2 \in \mathbb Z\;$"} \\ & \langle \exists q \in \mathbb Z :: q \cdot d = q_1 \cdot d - q_2 \cdot d \rangle \\ \equiv & \;\;\;\;\;\text{"divide by $\;d\;$; move $\;d = 0\;$ out of $\;\exists q\;$"} \\ & d = 0 \;\lor\; \langle \exists q \in \mathbb Z :: q = q_1 - q_2 \rangle \\ \equiv & \;\;\;\;\;\text{"one-point rule"} \\ & d = 0 \;\lor\; (q_1 - q_2) \in \mathbb Z \\ \equiv & \;\;\;\;\;\text{"right hand part is true since $\;q_1,q_2 \in \mathbb Z\;$"} \\ & \text{true} \\ \end{align}

This proves $(1)$.