1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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: Prove log_2(m) is not an integer.

  1. Dec 18, 2012 #1
    1. The problem statement, all variables and given/known data
    Let [itex]m[/itex] be a positive integer that has an odd divisor greater than [itex]1[/itex]. Prove (by contradiction) that [itex]\log_2{m}[/itex] is not an integer.

    2. Relevant equations

    3. The attempt at a solution
    I'm not sure where to begin here. The book I'm working with provides a similar example, but it was more specific and straightforward than this one (prove [itex]\log_2{19}[/itex] isn't an integer).

    I think I'm having the most trouble with grasping the part saying "m has an odd divisor greater than 1." How do I interpret that?
  2. jcsd
  3. Dec 18, 2012 #2


    User Avatar
    Homework Helper

    m is divisible by an odd prime (since all odd numbers greater than 1 are either prime or products of odd primes).
  4. Dec 18, 2012 #3


    User Avatar
    Science Advisor

    "m has an odd divisor greater than 1" simply means that m is NOT a power of 2.
    Given any number, we can factor out all factors of 2 to get the form [itex]2^n x[/itex] where x has no factors of 2 (and so is odd) and n is an integer. If x= 1, of course, that is a power of 2. If x> 1, it is not.

    If [itex]y= log_2(m)[/itex] then [itex]m= 2^y[/itex]. If y were an integer, then m would be a power of 2.
  5. Dec 18, 2012 #4
    Ah, I think I get it now. Here's the proof:

    Assume [itex]\log_2{m}[/itex] is an integer. Let [itex]y = \log_2{m}[/itex].
    Then, [itex]2^y = m[/itex].

    Since [itex]y[/itex] is assumed to be an integer, [itex]m[/itex] is a power of 2. This contradicts the fact that [itex]m[/itex] has an odd divisor greater than 1. Therefore, [itex]\log_2{m}[/itex] is not an integer.

    Thanks for the help!
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook