Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
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.
Proof by contradiction.
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.
