A little stumped on a number theory question

  • Thread starter bitshift
  • Start date
  • #1
3
0

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 [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.
 
Last edited:

Answers and Replies

  • #2
mjsd
Homework Helper
726
3
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.
 
  • #3
3
0
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.
 
  • #4
3
0
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...
 
Last edited:
  • #5
mjsd
Homework Helper
726
3
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.
 
  • #6
matt grime
Science Advisor
Homework Helper
9,395
3
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.
 
  • #7
MathematicalPhysicist
Gold Member
4,219
172
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.
 
  • #8
HallsofIvy
Science Advisor
Homework Helper
41,806
932
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?
 
  • #9
MathematicalPhysicist
Gold Member
4,219
172
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.
 
  • #10
matt grime
Science Advisor
Homework Helper
9,395
3
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.
 
  • #11
MathematicalPhysicist
Gold Member
4,219
172
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.
 
  • #12
matt grime
Science Advisor
Homework Helper
9,395
3
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.
 
  • #13
MathematicalPhysicist
Gold Member
4,219
172
yes i can see your point, is it a valid proof though?
 
  • #14
MathematicalPhysicist
Gold Member
4,219
172
btw, outside britain are there any others who use the term hcf, i thought everyone is using gcd. (-:
 
  • #15
matt grime
Science Advisor
Homework Helper
9,395
3
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.
 
  • #16
mathwonk
Science Advisor
Homework Helper
10,820
983
use contradiction. i.e. suppose a/b is not an integer, and prove no power of it is an integer.
 
  • #17
10
0
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
 
  • #18
MathematicalPhysicist
Gold Member
4,219
172
what do you think i tried to do on post number 7?
 
  • #19
matt grime
Science Advisor
Homework Helper
9,395
3
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.
 
  • #20
mathwonk
Science Advisor
Homework Helper
10,820
983
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.
 
  • #21
10
0
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
 
  • #22
mathwonk
Science Advisor
Homework Helper
10,820
983
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.
 
  • #23
Gib Z
Homework Helper
3,346
5
Lol so many misunderstandings and apologies, just be content that the math is now understood =)
 

Related Threads on A little stumped on a number theory question

Replies
16
Views
2K
  • Last Post
Replies
8
Views
633
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
4
Views
2K
Replies
1
Views
2K
  • Last Post
Replies
15
Views
2K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
3
Views
1K
Replies
3
Views
483
Top