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

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.

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.

• Great. This is exactly what I was looking for. I had a feeling Bezout had a role to play in this proof. – Charles Hudgins May 20 '19 at 20:53

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 contradiciton. So $$a\mid x$$.

• Which Gauss's lemma? Showing $a | xb \implies a |x$ when $(a,b) = 1$ is the part I wasn't sure about. – Charles Hudgins May 20 '19 at 20:48
• @CharlesHudgins: This lemma (which Wikipedia names after Euclid but some other sources name after Gauss) looks relevant in the context. – hmakholm left over Monica May 20 '19 at 20:50
• @MariaMazur it is intuitively clear, but making the argument formal is where I got confused. – Charles Hudgins May 20 '19 at 20:52
• This winds up being the same as the original proof I gave, which I considered inelegant. But maybe it could be written up more concisely than I originally thought. – Charles Hudgins May 20 '19 at 20:57