1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Well, noting that $m\,|\,m$ might help. $\endgroup$ – lulu Feb 18 at 11:12
  • $\begingroup$ That is certainly true, but I do not see how we can use it. $\endgroup$ – John P. Feb 18 at 11:15
  • $\begingroup$ Just apply the statement using $z=m$. $\endgroup$ – lulu Feb 18 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 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 at 11:26
6
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

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".

| cite | improve this answer | |
$\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.