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
    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
    Staff Emeritus
    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
    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
    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
    yes i can see your point, is it a valid proof though?
     
  15. Apr 4, 2007 #14
    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
    2015 Award

    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
    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
    2015 Award

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: A little stumped on a number theory question
  1. Number Theory Question (Replies: 9)

Loading...