Prove that every positive integer different from 1 can be expressed as a product of a non negative power of 2 and an odd number.

It is clear that any odd number can be written as the
product of a non-negative power of 2 and an odd number. Let n be an odd number. Then n =
2^0 * n = 1 * n = n.

For even numbers, we can take
advantage of the Fundamental Theorem of Arithmetic. The Fundamental Theorem of
Arithmetic states that every integer can be written as the product of prime
numbers.

It follows directly that an even number n will
have 2 as a prime factor. Let n be an even number, and the prime factorization of n =
(2^k * p1 * ... * pn), where k is some positive integer, and p1, ..., pn are primes.
Since p1, ..., pn are prime numbers greater than two, they are necessarily odd,
therefore their product is also odd. Thus n can be written as the product of a power of
two and an odd number.

Note that is n is a power of two, it
can simply be written as n = 2^k * 1, since 1 is an odd number.