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

- Feb 15th 2010, 12: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.

- Feb 15th 2010, 01: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 $\displaystyle 2^{p_a}O_a$ and $\displaystyle 2^{p_b}O_b$. This number has a unique decomposition into primes, from which it immediately follows that $\displaystyle p_a = p_b$, since $\displaystyle O_a$ and $\displaystyle O_b$ contain no factors of 2, and 2 is prime. Thus $\displaystyle 2^{p_a} = 2^{p_b} = c$. Now $\displaystyle cO_a = cO_b$, and since $\displaystyle c \geq 1$, it follows that $\displaystyle O_a = O_b$, 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.

- Feb 15th 2010, 01: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.

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

$\displaystyle 2^{p_1}3^{p_2}5^{p_3}...$

Now, using associativity, this is equal to

$\displaystyle 2^{p_1} \cdot (3^{p_2}5^{p_3}...)$

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. - Feb 15th 2010, 04:31 PMtarheelborn
Thank you!!!(Rofl)