# Prove log_2(m) is not an integer.

1. Dec 18, 2012

### SithsNGiggles

1. The problem statement, all variables and given/known data
Let $m$ be a positive integer that has an odd divisor greater than $1$. Prove (by contradiction) that $\log_2{m}$ 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 $\log_2{19}$ 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. Dec 18, 2012

### pasmith

m is divisible by an odd prime (since all odd numbers greater than 1 are either prime or products of odd primes).

3. Dec 18, 2012

### HallsofIvy

Staff Emeritus
"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 $2^n x$ 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 $y= log_2(m)$ then $m= 2^y$. If y were an integer, then m would be a power of 2.

4. Dec 18, 2012

### SithsNGiggles

Ah, I think I get it now. Here's the proof:

Assume $\log_2{m}$ is an integer. Let $y = \log_2{m}$.
Then, $2^y = m$.

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

Thanks for the help!