Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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 3

up vote 8 down vote accepted

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$

share|improve this answer
2  
+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$.

share|improve this answer
    
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$.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.