
Re: Power of 2 divisible by 3
Posted:
Jan 30, 2006 4:02 PM


Chip Eastham wrote:
> [...] > One can set aside the theory of primes and give a direct > proof by induction, based on 1 + 2 = 3. From this clearly > 3 does not divide 2 = 2^1, so that's the basis step. > > Suppose 3 does not divide 2^k (the induction hypothesis). > Then from 1 = 3  2, we multiply both sides by 2^k: > > 2^k = 3*(2*k)  2*(k+1) > > Now if (for the sake of contradiction) one assume 3 will > divide 2^(k+1), then 3 divides both terms on the right > hand side and must also divide the left hand side 2^k. > This contradicts the induction hypothesis, so the > assumption that 3 will divide 2^(k+1) must be false.
Niiiiiceeee!!!!
It's always refreshing seeing some "unconventional thinking" that puts aside the obvious ("the obvious" in this case being the fundamental theorem of arithmetic) to come up with a simple, nice, refreshing proof like the above.
Carlos 

