- Thread starter
- #1

- Thread starter KOO
- Start date

- Thread starter
- #1

If n is odd, we can write it as [tex]\displaystyle \begin{align*} n = n \cdot 2^0 \end{align*}[/tex].Prove that every n E N can be written as a product of odd integer and a non-negative integer power of 2.

For instance: 36 = 2^{2}* 9

If n is even (including 0), it must have a factor of 2, so we can write it as [tex]\displaystyle \begin{align*} n = 2^1 k \end{align*}[/tex].

Q.E.D.

- Jan 30, 2012

- 2,518

This is not enough to prove the required claim.If n is odd, we can write it as [tex]\displaystyle \begin{align*} n = n \cdot 2^0 \end{align*}[/tex].

If n is even (including 0), it must have a factor of 2, so we can write it as [tex]\displaystyle \begin{align*} n = 2^1 k \end{align*}[/tex].

- Aug 30, 2012

- 1,176

What about powers of 2? 2^k (k being a positive integer) has no odd factors, unless you want to include 1.Prove that every n E N can be written as a product of odd integer and a non-negative integer power of 2.

For instance: 36 = 2^{2}* 9

-Dan

- Jan 30, 2012

- 2,518

Well, weWhat about powers of 2? 2^k (k being a positive integer) has no odd factors, unless you want to include 1.

Obviously, a proof of this fact uses repeated division by 2. It can be made precise using strong induction.

There was another thread here about MathStackExchange (MSE), and the format that encourages dialogue was mentioned as a feature that distinguishes this forum from MSE. So I suggest that the OP write his/her reaction to what has been said so far and also the topic that this problem is supposed to teach (such as strong induction, direct proofs, or divisibility).