# Number Theory: Product of Power of Two

I'm having trouble solving the following number theory problem in my textbook:

Let a $\in Z$ with $a > 0$. Prove that there exists $k, n \in Z$ with n odd such that $a = 2^k n$

So far I've tried writing $n$ as an odd integer (i.e. n = 2q + 1) and then reducing somehow but that doesn't seem to be the correct way to solve it because I can only prove that $a$ can be even and not odd.

Any help would be appreciated?

-
k can be 0. (padding for 30 char minimum ......) –  marty cohen Jan 23 '13 at 18:28

You could use (strong) induction. The result is certainly true for $a=1$. Suppose that the result is true for all positive integers $i \lt a$. We show the result must hold for $a$.

There are two possibilities: (i) $a$ is odd and (ii) $a$ is even.

(i) If $a$ is odd, the result is trivially true for $a$, since $a=2^0a$.

(ii) If $a$ is even, let $a=2c$. Since $c\lt a$, by the induction assumption, the result is true for $c$. That is, there exist $j$, $w$, with $w$ odd, such that $c=2^j w$. But then $a=2^{j+1}w$, so the result is true for $a$.

-
is "b" suppose to be "a" in my problem description? Some of the letters are a little confusing. –  Math_Illiterate Jan 23 '13 at 18:43
You can call it $a$. I somewhat prefer a new letter, but maybe $a$ makes the logic clearer to you. –  André Nicolas Jan 23 '13 at 18:49

Prime factorization: $$a=\prod_{p\in P} p^{e_i}=2^{e_1}\prod_{p\not=2}p^{e_i}=2^k\cdot n$$ where $k=e_1$ and $n$ is a product of odd primes.

-

I will assume $0\in\mathbb{N}$.

Define $ord_2 : \mathbb{N}\rightarrow \mathbb{N}$ as $ord_2(a)$ is the highest power of $2$ that divides $a$. Since $a$ is a number $ord_2(a)$ will be finite and well-defined. Let $ord_2(a)=k$. You have that $2^k|a$, but by definition $2^{k+1}\nmid a$. Therefore, you can write $a=2^k\cdot n$ from the first conclusion. The second conclusion establishes that $n$ is odd. Your integers therefore are $k=ord_p(a)$ and $n=\frac{a}{ord_p(a)}$.

-