# Positive integer not a power of 2 has an odd prime factor

It's given that if a positive integer $n$ is Not a power of two, then $n$ must have an odd prime factor, meaning $$n = pr, p>2, 1\leq r< n$$ Is it really this trivial? There's a proof that uses this result, without even giving an explanation why it's true. If we assume $p=2$ why is that a contradiction?

Attempt: If $r=1$, then $n = 2\cdot 1$, which is a power of two, hence contradiction.
Assume $n = 2k$ is a power of two, then $n=2(k+1) = 2k+2\cdot 1$, but there's no contradiction.

• $1$ is a bit of an odd case since it doesn't really have any prime factors, but it's true for $n \gt 1$. – DylanSp Feb 12 '16 at 16:09
• Just writing $n=pr$ does not imply $p=2$, there is no contradiction. – Sergio Feb 12 '16 at 16:12

Hint Prove by induction that every integer $n>1$ can be written uniquely as $$n=2^k \cdot m$$ with $m$ odd. This can also be proven using the prime factorization.

Hint 2: If $n$ is not a power of $2$ then $m$ is an odd number and $m>1$. This $m$ is divisible by a prime $p$. What can you say about $p$?

If $n$ is not a power of two, then it has a prime factor which is not two, by definition.

• by whose definition? – Alvin Lepik Feb 12 '16 at 16:10
• Any definition! If the only prime factor is two, then it's a power of two. – Nick Matteo Feb 12 '16 at 16:10
• Wait, what? You claim that if a product contains two as a factor then the product is a power of two??? – Alvin Lepik Feb 12 '16 at 16:12
• If the only prime factor is two, then it's a power of two. – Nick Matteo Feb 12 '16 at 16:15
• @Kundor it does not come merely from a definition. You need to use the fact that every number can be written as a product of primes. – Sergio Feb 12 '16 at 16:17

If $n > 1$ has no odd prime factor, then only prime factor of $n$ is $2$. So $n = 2^k$ for some $k > 0$ from fundamental theorem of arithmetic.