Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Power of 2 divisible by 3
Replies: 19   Last Post: Feb 1, 2006 10:37 PM

 Messages: [ Previous | Next ]
 Bill Dubuque Posts: 1,739 Registered: 12/6/04
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