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.

Matthew Fonda | Certified Educator

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.