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

AI Thread Summary
Every natural number can be expressed as a product of an odd integer and a non-negative integer power of 2. For odd integers, this is straightforward as they can be represented as n multiplied by 2^0. Even integers, including zero, can be factored into 2 raised to a positive integer and another integer. The discussion emphasizes the importance of including 1 as an odd factor when considering powers of 2. A proof can be constructed using repeated division by 2 and strong induction to validate this claim.
KOO
Messages
19
Reaction score
0
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 = 22 * 9
 
Physics news on Phys.org
KOO said:
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 = 22 * 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.
 
Prove It said:
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.
 
KOO said:
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 = 22 * 9
What about powers of 2? 2^k (k being a positive integer) has no odd factors, unless you want to include 1.

-Dan
 
topsquark said:
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).
 
Back
Top