1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ $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$. $\endgroup$ – DylanSp Feb 12 '16 at 16:09
  • $\begingroup$ Just writing $n=pr$ does not imply $p=2$, there is no contradiction. $\endgroup$ – Sergio Feb 12 '16 at 16:12
2
$\begingroup$

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$?

$\endgroup$
1
$\begingroup$

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

$\endgroup$
11
  • 1
    $\begingroup$ by whose definition? $\endgroup$ – Alvin Lepik Feb 12 '16 at 16:10
  • $\begingroup$ Any definition! If the only prime factor is two, then it's a power of two. $\endgroup$ – Nick Matteo Feb 12 '16 at 16:10
  • $\begingroup$ Wait, what? You claim that if a product contains two as a factor then the product is a power of two??? $\endgroup$ – Alvin Lepik Feb 12 '16 at 16:12
  • $\begingroup$ If the only prime factor is two, then it's a power of two. $\endgroup$ – Nick Matteo Feb 12 '16 at 16:15
  • $\begingroup$ @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. $\endgroup$ – Sergio Feb 12 '16 at 16:17
1
$\begingroup$

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.

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.