It's easy to use prime factorization to show:
If $m\mid n^2$ then $\gcd(m,n^2/m)\mid n$.
Can anybody find some other proof - perhaps a simple reduction of some sort? Maybe solving $m^2x + n^2y=mn$, for example?
I suppose the result would follow if you could prove that $\gcd(m^2,n^2)=\gcd(m,n)^2$, since $\gcd(m,n)^2\mid mn$ since $\gcd(m,n)\mid m$ and $\gcd(m,n)\mid n$. That result doesn't even need $m\mid n^2$.
On
Oh, this all follows from the result that if $\gcd(a,b)=1$ then $\gcd(a^2,b^2)=1$. This is true since if $ax+by=1$ then $$1=(ax+by)^3 = a^2X+b^2Y.$$
So we deduce that $\gcd\left(\frac{n^2}{\gcd(n,m)^2}\,,\frac{m^2}{\gcd(n,m)^2}\right)=1$, and hence that $\gcd(m^2,n^2)=\gcd(m,n)^2$, and hence that $m^2x+n^2y=mn$ has a solution.
On
By here $\,\color{#0a0}{(m^2,n^2)} = (m,n)^2 = (m^2,\color{#c00}{mn},n^2)\Rightarrow \color{#0a0}{(m^2,n^2)}\mid \color{#c00}{mn} \overset{\!\div\,m}\Rightarrow (m,n^2/m)\mid n$
Since $m \mid n^2$, we have $n^2 = dm$ for some integer $d$. Inserting into the equation $m^2 x + n^2 y = mn$ gives $$ m^2x + dmy = mn\\ mx + dy = n\\ \gcd(m, d) \mid n $$ But $\gcd(m, d)^2 \mid md$, and we had $md = n^2$, so we're done.