# Show that $a^n \mid b^n$ implies $a \mid b$

I would like to show that $a^n \mid b^n$ implies $a \mid b$

I thought I could convert it to congruences and work backwards, but as far as I remember, $a \equiv b \pmod{m}$ implies $a^n \equiv b^n \pmod{m}$, not the opposite, unless $m$ is prime. Is that right?

So I am not sure how to approach this one. Any ideas?

Thanks!

-
This has got to be a repeat... –  Arturo Magidin Mar 8 '11 at 4:34
Didn't find anything in the search. –  Christoph Mar 8 '11 at 4:50
Me neither, but I'm sure I've seen this before... –  Arturo Magidin Mar 8 '11 at 5:06
@Arturo could this be what you recalled? math.stackexchange.com/questions/15326/… –  Arjang Mar 8 '11 at 6:07
@Arjang: No. But it's possible it's just deja vu from sci.math... –  Arturo Magidin Mar 8 '11 at 6:09

## 3 Answers

HINT $\:$ For $\rm\ c = b/a\$ it is $\rm\ c^n = d\in \mathbb Z\ \Rightarrow\ c\in \mathbb Z\:.\:$ Now apply the Rational Root Test to $\rm\ x^n-d\:.$

Notice again, just as in your prior few questions, converting it from divisibility relational form into equational form helps us to solve it efficiently. Here it allows us to notice that the problem is simply the special monic case of the Rational Root Test. Recall that this says that the leading coefficient of a polynomial $\rm\ f(x)\in \mathbb Z[x]\$ serves as a denominator for all its rational roots. In particular, when the leading coefficient is one this implies that every rational root can be written with denominator $= 1$, i.e. is an integer. This is a fundamental property in number theory. Indeed it is the property that is used to generalize the notion of integer from rationals to algebraic number fields.

For some generalizations see my post here. Here's a pertinent excerpt:

THEOREM $\:$ TFAE for $\rm\: a,b\:$ in domain $\rm\:Z\:,\ \: r \in Q \:=\:$ fraction field of $\rm\: Z\:,\ n\in \mathbb N$

$(1)\ \ \rm\ \ r = \sqrt[n]a \ \Rightarrow\ r \in Z$

$(2)\ \ \rm\ \ r^n \in \:Z \ \ \Rightarrow\ r \in Z$

$(3)\ \ \rm\ \ \ a^n\:|\:b^n \ \ \Rightarrow\:\ a\:|\:b$

$(4)\ \ \rm\ \ (a^n) = (b^n,\: c^n) \ \Rightarrow\ (a) = (b,c)\$ as ideals in $\rm\:Z$

-
+1 This is a really nice way of proving this. I should include this in my "bag of tricks". –  Adrián Barquero Mar 8 '11 at 4:34

Hint:

Write $b^n = q_1^{n \alpha_1} \dots q_k^{n \alpha_k}$, where $\alpha_i > 0$. If $a^n | b^n$, then $a^n = q_1^{n \beta_1} \dots q_k^{n \beta_k}$, where $0 \leq \beta_k \leq \alpha_k$.

-
I was wondering if this could be proved like, and then see this tab in google chrome open, and it had exactly the same problem with you giving a hint for exactly the same prove :) –  alcuadrado Mar 8 '11 at 6:22

Any prime $p$ that divides $a$ $k$ times, is such that $p^n$ divides $a^n$ $nk$ times and thus $b^n$ as well. But if a prime divides $b^n$ $nk$ times, it divides $b$ $k$ times as well. So every prime divisor of $a$ is one of $b$, with at least the same multiplicity.

Or use that $(b-a)$ divides $b^n - a^n$ for all $n \ge 1$.

-
Use $\rm\ b-a\ |\ b^n - a^n\$ for what? –  Bill Dubuque Mar 10 '11 at 19:29
This was an idea that does not work, I now see. –  Henno Brandsma Mar 10 '11 at 21:36