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: Number theory factorization proof

  1. Feb 3, 2009 #1
    1. The problem statement, all variables and given/known data
    1. The problem statement, all variables and given/known data

    If n is a nonzero integer, prove that n cam be written uniquely in the form n=(2^k)m, where It is in the primes and unique factorization chapter so maybe that every integer n (except 0 and 1) can be written as a product of primes


    2. Relevant equations


    It is in the primes and unique factorization chapter so maybe that every integer n (except 0 and 1) can be written as a product of primes


    3. The attempt at a solution

    I am not sure, but I tried to do a proof by induction on n

    Let n=1
    so, 1=(2^k)(m)
    1=(1)(1)=1 where k=0 and m=1
    so the statement holds for n=1

    Now assume the statement holds for n=(r-1) for any integer (except 0 and 1)
    so
    (r-1)=(2^k)(m) where k is greater than or equal to zero and m is odd

    Now let n=r
    so r=(2^k)(m)

    This is where I don't know what to do.... that is why i'm thinking there is an easier way to do this besides induction. Any help would be appreciated =)
     
  2. jcsd
  3. Feb 3, 2009 #2

    Mark44

    Staff: Mentor

    You left off the conditions in your problem statement.
    After this you tell us where the problem appeared in your text. What are the conditions on k and m?

    Also, for your induction proof, I would start with 2, not 1.
     
  4. Feb 3, 2009 #3
    ohh i'm sorry

    k has to be greater than or equal to zero and m is odd
     
  5. Feb 3, 2009 #4
    Let me repost the problem, cause I see some typos....

    Let n be a nonzero integer, prove that n can be written uniquely in the form (2^k)(m) for any integer k greater than or equal to zero and for any odd integer m.

    If i can avoid doing an induction proof, that would be great, but if this is the only way then i guess i can do it
     
  6. Feb 4, 2009 #5

    Mark44

    Staff: Mentor

    This might not pass muster as a formal proof, but it will help you think about this problem.

    There are two cases: n is even and n is odd.
    1) If n is odd, it has no factors of 2, so n = 20*n, and you're done.
    2) If n is even, there must be at least one factor of 2, so n = 21*m
    a) If m is odd, you're done.
    b) If m is even, apply step 1 again.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook