Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
    
k can be 0. (padding for 30 char minimum ......) –  marty cohen Jan 23 '13 at 18:28
add comment

3 Answers

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|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
add comment

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|improve this answer
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.