Question

Prove that every positive integer is uniquely representable as the product of non-negative power of 2 and odd number.

Answer 1

The fundamental theorem of arithmetic, which states that every positive integer greater than 1 can be uniquely factored into prime numbers.

Let's denote a positive integer n as the product of 2k and an odd number m, where k is a non-negative integer.

So, n = 2k × m, where m is an odd number.

Now, let's prove that such a representation is unique:

1. Existence of Representation: Every positive integer can be represented in this form. If n is odd, then k = 0 and m = n. If n is even, then repeatedly divide n by 2 until we get an odd quotient and the power of 2 used in the division. This gives us the representation n = 2^k × m.

2. Uniqueness of Representation: Suppose there exist two representations of the same positive integer n as: n = 2^k1 x m₁ = 2^k2 x m₂  where k₁​, k₂​ are non-negative integers and m₁​, m₂​ are odd numbers.

   Without loss of generality, assume k₁ ​≤  k₂​.

   Then, we have: 2^k1​ × m₁​ = 2^k2​ × m₂​ Divide both sides by 2^k1​: m₁​ = 2^k2​−k1 ​× m₂​

   Since m₁​ is odd, this implies that k₂ ​ −k_1​ = 0 (otherwise, the right side would be even).

   Thus, k₁​=k_2​ and hence, m₁​=m₂​.

   Therefore, the representation is unique.

Hence, every positive integer is uniquely representable as the product of a non-negative power of 2 and an odd number.