0

Let $n$ be an integer. Prove that there exist $k, m$ integers such that $n=2^km$.

I am stuck with this proof. I thought at first that I need to use contradiction but that did not work. What do you suggest? I know I have to break them into cases basically when $n=1$ then $1=2^0 \cdot 1$ but what about the other case?

pjs36
  • 17,979
Jamie John
  • 237
  • 3
  • 12
  • 2
    I suspect there are some missing criteria, otherwise one may choose $k = 0$ and $m = n$, since $n = 2^0 \cdot n$. – pjs36 Feb 13 '17 at 00:05
  • Related http://math.stackexchange.com/questions/1998419/how-to-prove-partition/ – rtybase Feb 13 '17 at 00:06
  • If you don't say what kind of integers are you considering, you can easily generalized to $n=p^km$ for all prime $p$ – Piquito Feb 13 '17 at 00:34

2 Answers2

0

Induction argument hint. Do the basis step. Then for the inductive step, assume it holds for $1, \dots, n$. Now take two cases: If $m$ is odd, you are done (why?). If $n$ is even consider $(n+1)/2$.... you fill in the rest.

abnry
  • 14,664
-1

Hint:

Consider the factorisation of $n$ as a product of primes: $$n=2^k\prod_{\substack{p_i\;\text{odd}\\\text{prime}}} p_i^{k_i}.$$

Bernard
  • 175,478