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.