A little stumped on a number theory question

bitshift · Apr 2, 2007

Hey, I'm a little stumped on this basic number theory question. The solution is probably staring me in the face, but for some reason it's eluding me...

If [tex]a^n | b^n[/tex], prove that [tex]a|b[/tex].

So, say that [tex]a^n \cdot x = b^n[/tex] for some integer [tex]x[/tex], there's not a lot I can go to from there. We do get that [tex]a | b^n[/tex] and that [tex]a^k | b^n[/tex] for all [tex] k \leq n[/tex], but I can't find a way in which that's useful.

I also tried using induction on [tex]n[/tex]. The base case is trivial. For the inductive case, assume that [tex]a^n | b^n[/tex] implies that [tex]a | b[/tex]. Then we must prove that [tex] a^{n+1} | b^{n+1} [/tex] implies that [tex] a|b[/tex]. So assume that [tex] a^{n+1} | b^{n+1}[/tex]. Then we get [tex]a^n | b^{n+1}[/tex], but I actually would need to show that [tex]a^n | b^{n} [/tex] and I can't figure out how to get there.

Am I totally missing something? I think I'm overthinking this. Nothing is coming. I'd appreciate any ideas on what to try next. Thanks.

mjsd · Apr 2, 2007

you may try analyse this using prime factors decomposition of a and b respectively. you can put constrains on what [tex]\frac{b^n}{a^n}[/tex] looks like and hence deduce what must happen to b/a.

bitshift · Apr 2, 2007

Thanks for the reply!

I was wondering if the prime factorization would be of any use, since it seems like we need to prove something about the quotient (that its nth root is an integer).

I can write [tex]a = p_1^{i_1} \cdots p_k^{i_k}[/tex] and b = [tex]q_1^{j_1} \cdots q_{\ell}^{j_{\ell}}[/tex], where all the p's and q's are prime. Then [tex]\frac{b^n}{a^n} = \frac{q_1^{nj_1} \cdots q_{\ell}^{nj_{\ell}}}{p_1^{ni_1}\cdots p_k^{ni_k}} \in \mathbb{Z}[/tex].

I guess some of these prime factors must cancel... hmm. I'll think about it.

bitshift · Apr 2, 2007

Ok, considering the quotient

[tex] Q = \frac{b^n}{a^n} = \frac{q_1^{nj_1} \cdots q_{\ell}^{nj_{\ell}}}{p_1^{ni_1}\cdots p_k^{ni_k}}[/tex]

we have, since [tex]Q \in\mathbb{Z}[/tex], that every prime factor in the denominator must also appear at least that many times in the numerator (I'm a little unsure about justifying this step, it seems obvious, because otherwise we would have a fraction in lowest terms, which would imply that Q is not an integer).

Now we're left with a product of primes. It seems clear that the q's that got canceled out will still each be raised to a power that is a multiple of n, because, say for some [tex]m[/tex], we have [tex]q_m = p_m[/tex]. Then we take [tex]q_m^{nx}[/tex] (where x is the exponent of [tex]q_m[/tex] as it appears in the factorization of [tex]b^n[/tex]) and divide it by a factor [tex]p_t^{ny}[/tex] where [tex]p_t = q_m[/tex] and is in the factorization of the denominator. We do this for each prime power in the denominator. We're left with a sequence of primes, each raised to a power that is a multiple of [tex]n[/tex]. So... their product's nth root is an integer, since the nth root of each prime power is just some other (integral) power of that prime.

There are a few details left out, but that's almost beginning to convince me. I wonder if there is a less messy way to write this...

mjsd · Apr 2, 2007

if you use [tex]\frac{b^n}{a^n}=\left(\frac{b}{a}\right)^n[/tex] then it would be quite obvious as for real numbers [tex]x^n = 1[/tex] means x =1 when n is not zero.

matt grime · Apr 3, 2007

Way to complicated. Suppose there is a counter example. If there is one, then there is one with a as small as possible. If p is a prime dividing a, then p divides p^n divides b^n, hence p divides b, since p is a prime

But then a/p is a smaller counter example, which is a contradiction. Hence there are no counter examples.

MathematicalPhysicist · Apr 3, 2007

if b isnt divisible by a, then b^n/a^n=(b/a)^n=(c/d)^n where gcd(c,d)=1
so we get that b^n isnt divisble by a^n.

HallsofIvy · Apr 3, 2007

loop quantum gravity said: ↑

if b isnt divisible by a, then b^n/a^n=(b/a)^n=(c/d)^n where gcd(c,d)=1
so we get that b^n isnt divisble by a^n.

I'm not clear on this. Are you saying that (b/a)^n= (c/d)^n for any mutually prime c and d? Surely not. And if not, what are c and d?

If b is NOT divisible by a then b= ak+ c for integer k and non-zero integer c.
Can you now show that bⁿ is not divisible by aⁿ? What is (ak+ c)ⁿ?

MathematicalPhysicist · Apr 3, 2007

what im saying is because a doesnt divide b, then if we take the reduced fraction of b/a=c/d where (c,d)=1, then also b^n/a^n=(b/a)^n=(c/d)^n isn't an integer.
cause, (c^n,d^n)=(c,d)^n.

matt grime · Apr 4, 2007

And have you proved raising a non-integer to a power means you get a non-integer? As far as I can see, that is assuming the answer.

MathematicalPhysicist · Apr 4, 2007

isn't it implied from this (c^n,d^n)=(c,d)^n=1^n=1
so we have that (c/d)^n=c^n/d^n, where c^n and d^n have no common factors, thus this fraction is in Q but not in Z.
the only thing that might be bad here, is that if (c^n,d^n)=(c,d)^n is a consequence of what i need to prove bacuse if it is so, then obviously it doesnt work.

matt grime · Apr 4, 2007

loop quantum gravity said: ↑

isn't it implied from this (c^n,d^n)=(c,d)^n=1^n=1

If you're going to claim that then there is no reason to do any of what you did: the HCF of a^n and b^n is a^n, thus impliying that HCF of (a,b) is a automatically.

MathematicalPhysicist · Apr 4, 2007

yes i can see your point, is it a valid proof though?

MathematicalPhysicist · Apr 4, 2007

btw, outside britain are there any others who use the term hcf, i thought everyone is using gcd. (-:

matt grime · Apr 4, 2007

loop quantum gravity said: ↑

yes i can see your point, is it a valid proof though?

To avoid being circular you have to rely on a result which already implies the required result in far fewer steps. That doesn't make it invalid, just unnecessary.

mathwonk · Apr 4, 2007

use contradiction. i.e. suppose a/b is not an integer, and prove no power of it is an integer.

adityab88 · Apr 5, 2007

it's quite easy
prove by contradiction

i am very suprised that such an EASY question has stumbled so many of you people. you should be ashamed of yourselves

MathematicalPhysicist · Apr 5, 2007

what do you think i tried to do on post number 7?

matt grime · Apr 5, 2007

adityab88 said: ↑

it's quite easy
prove by contradiction

i am very suprised that such an EASY question has stumbled so many of you people. you should be ashamed of yourselves

who has it 'stumbled'*? No one as far as I can tell apart from the OP.

* I think you mean stumped, not stumbled. I can't believe that stumped you, figuring out that EASY piece of English.

mathwonk · Apr 5, 2007

adityab88, yiou should be ashamed of yourself for trying to embarrass people just because they do not solve a silly math problem.

there is no shame in not understanding math, but there is shame in trying to humiliate people.