Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
k can be 0. (padding for 30 char minimum ......) – marty cohen Jan 23 '13 at 18:28
up vote 1 down vote accepted

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

share|cite|improve this answer
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.

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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