Use the Fundamental Theorem of Arithmetic to show every positive integer, n>0, can be written uniquely as the product of a power of 2 and an odd number.

Printable View

- February 15th 2010, 01:51 PMtarheelbornFundamental Theorem of Arithmetic
Use the Fundamental Theorem of Arithmetic to show every positive integer, n>0, can be written uniquely as the product of a power of 2 and an odd number.

- February 15th 2010, 02:31 PMicemanfan
Suppose that there are two distinct representations of the same number as the product of a power of 2 and an odd number (let us call them and . This number has a unique decomposition into primes, from which it immediately follows that , since and contain no factors of 2, and 2 is prime. Thus . Now , and since , it follows that , thus demonstrating that the two representations are not distinct, and hence the number has a unique representation as a power of 2 and an odd number.

- February 15th 2010, 02:59 PMtarheelborn
I see where your proof shows uniqueness, but I don't see how it shows that the integers can be written as the product of a power of 2 and an odd number.

- February 15th 2010, 03:07 PMicemanfan
Oh, I guess I just overlooked that part because it seemed obvious. Write a number as its unique product of primes:

Now, using associativity, this is equal to

The left term is a power of two and the right term is an odd number, because every product of only odd numbers is odd. You can prove that statement easily using modular arithmetic. - February 15th 2010, 05:31 PMtarheelborn
Thank you!!!(Rofl)