Can Divisibility of Powers Imply Divisibility of Bases?

[bitshift]

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 a^n | b^n, prove that a|b.

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

I also tried using induction on n. The base case is trivial. For the inductive case, assume that a^n | b^n implies that a | b. Then we must prove that a^{n+1} | b^{n+1} implies that a|b. So assume that a^{n+1} | b^{n+1}. Then we get a^n | b^{n+1}, but I actually would need to show that a^n | b^{n} 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]

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

 

[bitshift]

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 a = p_1^{i_1} \cdots p_k^{i_k} and b = q_1^{j_1} \cdots q_{\ell}^{j_{\ell}}, where all the p's and q's are prime. Then \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}.

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

 

[bitshift]

Ok, considering the quotient

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}}

we have, since Q \in\mathbb{Z}, 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 m, we have q_m = p_m. Then we take q_m^{nx} (where x is the exponent of q_m as it appears in the factorization of b^n) and divide it by a factor p_t^{ny} where p_t = q_m 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 n. 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]

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

 

[matt grime]

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]

if b isn't 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 isn't divisble by a^n.

 

[HallsofIvy]

if b isn't 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 isn't 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]

what I am saying is because a doesn't 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]

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]

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 doesn't work.

 

[matt grime]

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]

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

 

[MathematicalPhysicist]

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

 

[matt grime]

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]

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

 

[adityab88]

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]

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

 

[matt grime]

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]

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.

 

[adityab88]

just read a number theory book

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.

i am sorry in that i did not mean it to come that way.

all i mean is that an answer to such a question is pretty standard and can be found in almost any number theory textbook. people can just read up the solutions. i did not mean to humiliate ppl.

sorry for any offence

 

[mathwonk]

please forgive me for piling on you for a little fault i myself am primarily guilty of.

this was a case of projecting ones own foibles onto others, on my part.

thank you for your generous comments.

 

[Gib Z]

Lol so many misunderstandings and apologies, just be content that the math is now understood =)