# Prove that if $m\mid z$ implies that $n \mid z$, then $n\mid m$

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?

• Well, noting that $m\,|\,m$ might help. – lulu Feb 18 at 11:12
• That is certainly true, but I do not see how we can use it. – John P. Feb 18 at 11:15
• Just apply the statement using $z=m$. – lulu Feb 18 at 11:16
• Are we allowed to do that, though, when we want to prove this fact for all $z$? – John P. Feb 18 at 11:18
• 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$. – lulu Feb 18 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".