> [...] > 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.
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.