Elegant Proof that $m | xn \implies \frac{m}{(m,n)} | x$

Question

I have a proof that shows $m | xn \implies \frac{m}{(m,n)} | x$ which leans heavily on prime factorizations. Is there a more straightforward proof?

Edit

With this question, I was looking for a proof that didn't involve Euclid's lemma (which is almost immediately equivalent to what is to be proved) or prime factorization. I think this question is worth keeping up if only for the answer below which establishes the result using Bezout's identity. None of the answers in the other post approach it this way.

Answer 1

Solve $mu+nv=(m,n).$ (Such a solution is guaranteed by Bézout's identity, which is usually a lemma on the way to unique factorization.)

Multiply by $x$ to get: $m(ux)+(nx)v=(m,n)x.$

But $m\mid m(xu)$ and $m\mid(nx)v$ so $m\mid (m,n)x.$

Hence $\frac{m}{(m,n)}\mid x.$

The last step is from:

Lemma: If $d\mid m$ and $m\mid xd$ then $\frac{m}{d}\mid x.$

which is easy to prove.

Answer 2

Let $d=(m,n)$ then $m=da$ and $n=db$, where $a,b$ are relatively prime.

From $$m\mid nx\implies da\mid xdb\implies a\mid xb\implies a\mid x$$

Last implication is true due to Gauss lemma. So $${m\over d}\mid x$$ and we are done.

---

We can avoid Gauss lemma. Suppose there exists $a,b$ relatively prime such that $a\mid xb$ and $a\nmid x$. Then among all such triples $(a,b,x)$ take the one with minimal $a$ and take any prime $p$ which divides $a$. Then it can not divide $b$ since $a,b$ are relatively prime. So $p$ must divde $x$. But now $a'\mid x'b$ where $x'={x\over p}$ and $a' = {a\over p}<a$. A contradiciton. So $a\mid x$.