Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

A little stumped on a number theory question

  1. Apr 2, 2007 #1
    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: Apr 2, 2007
  2. jcsd
  3. Apr 2, 2007 #2

    mjsd

    User Avatar
    Homework Helper

    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.
     
  4. Apr 2, 2007 #3
    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.
     
  5. Apr 2, 2007 #4
    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: Apr 2, 2007
  6. Apr 2, 2007 #5

    mjsd

    User Avatar
    Homework Helper

    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.
     
  7. Apr 3, 2007 #6

    matt grime

    User Avatar
    Science Advisor
    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.
     
  8. Apr 3, 2007 #7

    MathematicalPhysicist

    User Avatar
    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.
     
  9. Apr 3, 2007 #8

    HallsofIvy

    User Avatar
    Science Advisor

    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?
     
  10. Apr 3, 2007 #9

    MathematicalPhysicist

    User Avatar
    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.
     
  11. Apr 4, 2007 #10

    matt grime

    User Avatar
    Science Advisor
    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.
     
  12. Apr 4, 2007 #11

    MathematicalPhysicist

    User Avatar
    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.
     
  13. Apr 4, 2007 #12

    matt grime

    User Avatar
    Science Advisor
    Homework Helper


    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.
     
  14. Apr 4, 2007 #13

    MathematicalPhysicist

    User Avatar
    Gold Member

    yes i can see your point, is it a valid proof though?
     
  15. Apr 4, 2007 #14

    MathematicalPhysicist

    User Avatar
    Gold Member

    btw, outside britain are there any others who use the term hcf, i thought everyone is using gcd. (-:
     
  16. Apr 4, 2007 #15

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  17. Apr 4, 2007 #16

    mathwonk

    User Avatar
    Science Advisor
    Homework Helper

    use contradiction. i.e. suppose a/b is not an integer, and prove no power of it is an integer.
     
  18. Apr 5, 2007 #17
    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
     
  19. Apr 5, 2007 #18

    MathematicalPhysicist

    User Avatar
    Gold Member

    what do you think i tried to do on post number 7?
     
  20. Apr 5, 2007 #19

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  21. Apr 5, 2007 #20

    mathwonk

    User Avatar
    Science Advisor
    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.
     
  22. Apr 6, 2007 #21
    just read a number theory book

    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
     
  23. Apr 6, 2007 #22

    mathwonk

    User Avatar
    Science Advisor
    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.

    thank you for your generous comments.
     
  24. Apr 6, 2007 #23

    Gib Z

    User Avatar
    Homework Helper

    Lol so many misunderstandings and apologies, just be content that the math is now understood =)
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook