Can Every Integer Be Decomposed into an Odd Integer and a Power of 2?

[KOO]

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² * 9

 

[Prove It]

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² * 9

If n is odd, we can write it as \displaystyle \begin{align*} n = n \cdot 2^0 \end{align*}.

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

Q.E.D.

 

[Evgeny.Makarov]

If n is odd, we can write it as \displaystyle \begin{align*} n = n \cdot 2^0 \end{align*}.

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

This is not enough to prove the required claim.

 

[topsquark]

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² * 9

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

-Dan

 

[Evgeny.Makarov]

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

Well, we want to include 1. Thus, if $k$ is a nonnegative integer, then $2^k=1\cdot2^k$: here 1 is an odd integer and $2^k$ is a non-negative integer power of 2, so this factorization satisfies the problem statement.

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

There was https://driven2services.com/staging/mh/index.php?posts/33828/ 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).