# Does $a^n \mid b^n$ imply $a\mid b$?

Does $a^n \mid b^n$ imply $a\mid b$? I think it does but haven't been able to prove it. I don't know much number theory so an elementary answer would be great.

• Hint: Look at prime factors. – Brett Frankel Apr 5 '13 at 0:29
• You can start with the fundamental theorem of arithmetic. – Julien Apr 5 '13 at 0:30
• Consider this. Might I call yhis a duplicate? Since they end up in asking the same question. – awllower Apr 5 '13 at 13:32
• @awllower: you're right that it's a duplicate, but I think this one has better answers. – Javier Apr 5 '13 at 14:16
• @JavierBadia Probably because the previous one prohibited the use of GCD and UFD. – awllower Apr 5 '13 at 15:01

## 3 Answers

If you can assume the fundamental theorem of arithmetic (that each integer has a unique factorization in prime numbers), you can write: \begin{align*} a &= p_1^{e_1} p_2^{e_2} \ldots p_r^{e_r} \\ b &= q_1^{d_1} q_2^{d_2} \ldots q_s^{d_s} \end{align*} Here the $p_i$, $q_i$ are primes, and $e_i$ and $d_i$ are all greater than 0. If $a^n \mid b^n$, then $p_i^{n e_i}$ must have a counterpart in a $q_j^{n d_j}$, in that $p_i = q_j$ and $n e_i \le n d_j$, so it must then also be that $e_i \le d_j$; and this means $a \mid b$.

Hint $\$ Either examine exponents in unique prime factorizations, or, by the Rational Root Test, the reduced rational root $\rm\:x = b/a\:$ of $\rm\:x^n = c\in\Bbb Z\:$ must be integral, so $\rm\:b/a\in\Bbb Z\:\Rightarrow\:a\mid b.$

• @Peter For that, after cancelling any common factor, one needs only $\rm\:(a,b)=1\:\Rightarrow\:(a,b^n)=1,\:$ true by iterating Euclid's Lemma. Thus $\rm\:1 < a\nmid b^n,\:$ so $\rm\:a^n\nmid b^n.\ \$ – Math Gems Apr 5 '13 at 0:41
• Yes, that was my idea. I was awfully unclear, sorry. – Pedro Tamaroff Apr 5 '13 at 0:44

Hint: $p$ is a prime factor of $k$ if and only if $p^n$ is a factor of $k^n$. This holds for any prime $p$, integer $k$, and positive integer $n$.