
Re: Power of 2 divisible by 3
Posted:
Jan 30, 2006 9:19 PM


Carlos Moreno <moreno_at_mochima_dot_com@mailinator.com> wrote: >Chip Eastham wrote: (*edited and corrected*) >> >> 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 3  2 = 1, we multiply both sides by 2^k: >> >> k k k >> 3 2  2 2 = 2
i.e. 3  3 C & 2 C > 3C (= 3C2C), above C = 2^k
This is a very special case of Euclid's Lemma as I show below.
> 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.
But, in fact, this proof is an obvious specialization of the key Euclid's Lemma employed to prove the FTA = unique factorization:
LEMMA (Euclid) (a,b)=1 & abc > ac
PROOF Recall (a,b)=1 > ja+kb = 1 for some integers j,k
Therefore it follows that a(ja+kb)c = c [via aja, abc ] QED
For a,b = 3,2: 32c > 3( 3 2)c = c [here j=1, k=1 ]
k k+1 k k1 For c = 2 : 32 > 32 (> 32 >...> 31 >< )
The inference abc > a(a,b)c is ubiquitous in divisor theory
of the rational integers (or any PID), e.g. see my prior posts [1].
Note, however, for a fixed prime p (such as p = 3 above), one may directly prove the prime divisor property: pab > pb or pc by a brute force case analysis of the the finitely many choices for a, b (mod p). For p=3 it amounts to (+1)(+1) != 0 (mod 3).
Bill Dubuque
[1] http://google.com/groups?q=group%3A*math*+dubuque+euclid+lemma

