# A little stumped on a number theory question

## Main Question or Discussion Point

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.

Last edited:

Related Linear and Abstract Algebra News on Phys.org
mjsd
Homework Helper
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.

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.

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

Last edited:
mjsd
Homework Helper
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
Homework Helper
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
Gold Member
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
Homework Helper
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 bn is not divisible by an? What is (ak+ c)n?

MathematicalPhysicist
Gold Member
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
Homework Helper
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
Gold Member
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
Homework Helper
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
Gold Member
yes i can see your point, is it a valid proof though?

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

matt grime
Homework Helper
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
Homework Helper
use contradiction. i.e. suppose a/b is not an integer, and prove no power of it is an integer.

it's quite easy

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

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

matt grime
Homework Helper
it's quite easy

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
Homework Helper
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.

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
Homework Helper
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.

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