Other people have reduced the problem to a proof of:
Theorem: If $n^2\mid m^2$ then $n\mid m$.
There are lots of ways to prove this. I found what I think is a novel proof.
Proof: Let $d=\gcd(m,n).$ Then $d=mx+ny$ for some pair $x,y$. So $d^{2k+1}=(mx+ny)^{2k+1}$ for any integer $k\geq 0$. But the right side is divisible by $n^{2k}$, since each term in the expansion is a multiple of$m^{i}n^{2k+1-i}$ for some $i$. If $i=2j$ is even, then $n^{2j}\mid m^{2j}$, and $n^{2(k-j)}\mid n^{2k+1-2j}$. Likewise, for $i=2j+1$.
So this means that $d\mid n$ and $n^{2k}\mid d^{2k+1}$ for all $k$. This means that $\left(\frac nd\right)^{2k}\mid d$ for all $k$. If $d<n$, then $\frac{n}{d}>1$, so for some* $k$, $\left(\frac nd\right)^{2k}>d$, which is a contradiction.
So we must have $d=n$, and thus $n\mid m$.
This proof generalizes. If $n^a\mid m^a$ and $d=\gcd(m.n)=mx+ny$ then you can show that for all $k> 0$, $n^{ak}\mid d^{ak+a-1}$ for all $k$ and thus that $\left(\frac{n}{d}\right)^{ak}\mid d^{a-1}$ for all $k$, which means that $\left(\frac{n}{d}\right)^{ak}$ is bounded, so $n=d$ and $n\mid m$.
* (You can come up with the specific $k=d$. This is because $2^{2d}>2^d>d$ for all $d$, and (under the assumption) $\frac{n}{d}\geq 2$.)
You don't even need the full Bézout's identity, just some version of a division algorithm.
You do need:
Lemma: If $d<n$ then for infinitely many $k\in\mathbb N,$ we have that $d^{k+1}<n^k.$
From there, we can write $m=nq+d$, with $0\leq d<n.$ But if $d=0$ we are done. Otherwise, we have $d=m-nq,$ and we take the same tack, and get that $n^{ak}\mid d^{ak+a-1}$ for all $k$, which means that $(n^a)^k\leq (d^a)^{k+1}.$
An interesting example might be when $m,n\in R[x],$ where $R$ is some commutative ring with no nilpotents, and $n$ is monic. Then we can divide $m$ by $n$ and get a remainder $d$ of degree less than the degree of $n.$ Even though we might not get a full division algorithm in this ring, nor Bezout, but we can still conclude that if $n^a\mid m^a$ then $n\mid m.$
An alternative way of putting this is:
If $R$ is a commutative ring, and $m,n\in R[x]$ with $n$ monic and $n^a\mid m^a$ for some $a\geq 1$ then if $m=nq+d$ with $\deg(d)<\deg(n)$ then $d$ is nilpontent in $R[x].$