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

Homework Help: Fundamental Theorem of Arithmetic

  1. Feb 15, 2010 #1
    1. The problem statement, all variables and given/known data
    Using the Fundamental Theorem of Arithmetic, prove that every positive integer can be written uniquely as a power of 2 and an odd number.


    2. Relevant equations



    3. The attempt at a solution
    Since the FTOA states that any integer can be written as a product of primes, then it seems that any positive integer can be of the form 2^i*p^j, where p is a prime <> 2. But to get 1, I would have to have 2^0*p*0 and I'm not sure if that would work.
     
  2. jcsd
  3. Feb 15, 2010 #2

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Even 15?

    P.S. have you tried specific examples, rather than trying to prove it for everything right off the bat?
     
  4. Feb 15, 2010 #3
    Initially, I had worked this problem so that I was dealing with two cases, evens and odds. I came up with even integers = 2^0+(n-1) and odd integers = 2^1+(n-2). Hence 15 would equal 2+(15-2)=2+13. But I couldn't work that into a proof using FTOA. I am not sure whether I should try to multipy or add/subtract the odd number.
     
  5. Feb 15, 2010 #4

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    For some reason, I was sure the problem you wrote said "sum". Of course, the problem cannot be right in that case (you could use 4 as your power of 2, instead of 2, and get two different answers)

    If the problem said "product", then the representation is unique -- and it's a useful representation I've seen in actual application -- so that's probably what it meant.
     
  6. Feb 15, 2010 #5
    Actually, it didn't say either product or sum. It simply said that every positive integer can be written "uniquely as a power of 2 and an odd number." I believe it will have to be a product, so I will try developing a pattern as you suggested with actual numbers. I may be back, however! Thank you.
     
  7. Feb 15, 2010 #6
    The odd numbers seem to be working out nicely to 2^0 * n, but I am having trouble coming up with a pattern for the even numbers. Any ideas that could nudge along my thinking? Thank you.
     
  8. Feb 15, 2010 #7

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    If you can't figure out all even numbers, how about some of them?
     
  9. Feb 15, 2010 #8
    OK. I have the following (sometimes I feel really dense and this is certainly one of those times!) list:

    2=2^1*1
    4=2^2*1
    6=2^1*3
    8=2^3*1
    10=2^1*5
    12=2^2*3
    14=2^1*7

    So it seems like every other one (starting with 2) is 2^1 * (n/2). I don't see a pattern in the others.
     
  10. Feb 15, 2010 #9
    Keep in mind that 2^0 is a power of 2.
     
  11. Feb 15, 2010 #10
    So, using the Fundamental Theorem of Arithmetic would I be able to say that any integer can be written as a product of primes, implying that any integer can be written as 2^i * 3^j * 5^k... and then take out the power of 2 so that said integer can be written as 2*(3^j * 5^k...), where j, k >=0. With 2 out of the picture, the other elements of the product would be odd and odd numbers multiplied by odd numbers give odd numbers, so it is proved.

    Is that where I need to go? Thanks so much for your help!
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook