0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ k can be 0. (padding for 30 char minimum ......) $\endgroup$ – marty cohen Jan 23 '13 at 18:28
1
$\begingroup$

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

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

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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