Fundamental Theorem of Arithmetic

[tarheelborn]

Homework Statement

Using the Fundamental Theorem of Arithmetic, prove that every positive integer can be written uniquely as a power of 2 and an odd number.

Homework Equations

The Attempt at a Solution

Since the FTOA states that any integer can be written as a product of primes, then it seems that any positive integer can be of the form 2^i*p^j, where p is a prime <> 2. But to get 1, I would have to have 2^0*p*0 and I'm not sure if that would work.

 

[Hurkyl]

it seems that any positive integer can be of the form 2^i*p^j.

Even 15?

P.S. have you tried specific examples, rather than trying to prove it for everything right off the bat?

 

[tarheelborn]

Initially, I had worked this problem so that I was dealing with two cases, evens and odds. I came up with even integers = 2^0+(n-1) and odd integers = 2^1+(n-2). Hence 15 would equal 2+(15-2)=2+13. But I couldn't work that into a proof using FTOA. I am not sure whether I should try to multipy or add/subtract the odd number.

 

[Hurkyl]

For some reason, I was sure the problem you wrote said "sum". Of course, the problem cannot be right in that case (you could use 4 as your power of 2, instead of 2, and get two different answers)

If the problem said "product", then the representation is unique -- and it's a useful representation I've seen in actual application -- so that's probably what it meant.

 

[tarheelborn]

Actually, it didn't say either product or sum. It simply said that every positive integer can be written "uniquely as a power of 2 and an odd number." I believe it will have to be a product, so I will try developing a pattern as you suggested with actual numbers. I may be back, however! Thank you.

 

[tarheelborn]

The odd numbers seem to be working out nicely to 2^0 * n, but I am having trouble coming up with a pattern for the even numbers. Any ideas that could nudge along my thinking? Thank you.

 

[Hurkyl]

If you can't figure out all even numbers, how about some of them?

 

[tarheelborn]

OK. I have the following (sometimes I feel really dense and this is certainly one of those times!) list:

2=2^1*1
4=2^2*1
6=2^1*3
8=2^3*1
10=2^1*5
12=2^2*3
14=2^1*7

So it seems like every other one (starting with 2) is 2^1 * (n/2). I don't see a pattern in the others.

 

[e(ho0n3]

Keep in mind that 2^0 is a power of 2.

 

[tarheelborn]

So, using the Fundamental Theorem of Arithmetic would I be able to say that any integer can be written as a product of primes, implying that any integer can be written as 2^i * 3^j * 5^k... and then take out the power of 2 so that said integer can be written as 2*(3^j * 5^k...), where j, k >=0. With 2 out of the picture, the other elements of the product would be odd and odd numbers multiplied by odd numbers give odd numbers, so it is proved.

Is that where I need to go? Thanks so much for your help!