I am trying to prove the following divisibility fact:

For any $z \in \mathbb{Z}$, suppose $m \mid z$ implies that $n \mid z$. Then $n \mid m$.

The intuition here is not too difficult for me to grasp. If, for example, some $z$ always has a factor of $m$ implies that it always has a factor of $n$, that would suggest we can take a factor of $n$ out of $m$. I am having some difficult proving this fact rigorously, though.

A hint on how to proceed would be greatly appreciated. Is contradiction the appropriate approach?

  • 1
    $\begingroup$ Well, noting that $m\,|\,m$ might help. $\endgroup$
    – lulu
    Feb 18 '20 at 11:12
  • $\begingroup$ That is certainly true, but I do not see how we can use it. $\endgroup$
    – John P.
    Feb 18 '20 at 11:15
  • $\begingroup$ Just apply the statement using $z=m$. $\endgroup$
    – lulu
    Feb 18 '20 at 11:16
  • $\begingroup$ Are we allowed to do that, though, when we want to prove this fact for all $z$? $\endgroup$
    – John P.
    Feb 18 '20 at 11:18
  • 2
    $\begingroup$ You are told that $m,n$ are such that, no matter what $z$ is, $m\,|\,z\implies n\,|\,z$. That is given. Given that this is true you are asked to deduce that $n\,|\m$. $\endgroup$
    – lulu
    Feb 18 '20 at 11:26

Set $z=m$. Clearly $m \mid m$. We have: $$n \mid z \implies n \mid m$$ Done!

BTW we can substitute $z=m$ since the condition is: $$m \mid z \implies n \mid z$$ for any $z$.


It's clearer in terms of sets of multiples, where divides = contains by $\,(\color{#c00}{3\!\iff\! 2})\,$ below. The utility of this view becomes clear when one studies (principal) ideals or (cyclic) groups.

Lemma $ $ TFAE for $\,m,n\in\Bbb Z$

$(1)\ \ \, n\:\!|\:\!z\,\Leftarrow\, m\:\!|\:\!z,\ $ for all $\,z\in\Bbb Z$

$\!\left.\begin{align}&\color{#c00}{(2)}\ \ \ \ n\Bbb Z\,\supseteq\, m\Bbb Z\\[.5em] &\color{#c00}{(3)}\ \ \ \ \ \ \ n\,\mid\, m\end{align}\,\right\}\ $ [divides = contains]

Proof $\ \ (1\Rightarrow 2)\,\ \ z\in m\Bbb Z\,\Rightarrow\,m\mid z\Rightarrow\,n\mid z\,\Rightarrow\, z\in n\Bbb Z$
$(2\Rightarrow 3)^{\phantom{|^|}}\ \ m\in m\Bbb Z\subseteq n\Bbb Z\,\Rightarrow\, m\in m\Bbb Z\,\Rightarrow\,m = nz\,\Rightarrow\,n\mid m.\,$
$(3\Rightarrow 1)^{\phantom{|^|}}\ \ n\mid m\mid z\,\Rightarrow\, n\mid z\ $ by transitivity of "divides".


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.