|
|
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 -> 3|C (= 3C-2C), 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 & a|bc -> a|c
PROOF Recall (a,b)=1 -> ja+kb = 1 for some integers j,k
Therefore it follows that a|(ja+kb)c = c [via a|ja, a|bc ] QED
For a,b = 3,2: 3|2c -> 3|( 3 -2)c = c [here j=1, k=-1 ]
k k+1 k k-1
For c = 2 : 3|2 -> 3|2 (-> 3|2 ->...-> 3|1 -><- )
The inference a|bc -> 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: p|ab -> p|b or p|c
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
|
|
