1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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.$ $\endgroup$ – Cameron Buie Nov 18 '13 at 20:08
2
$\begingroup$

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$

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

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). $$

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

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)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.