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

Question

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?

Answer 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}.$$

Answer 2

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.