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


XleonardXcobetX@gmail.com wrote: > I cannot seem to find a power of 2 divisible by 3. I did all of the > powers up to 4096 in my head. Then I wrote a simple computer program > to try to find a power of 2 divisible by 3, but it couldn't find any. > So the number must be above 2^32. But what is the smallest power of 2 > divisible by 3? Does a number x such that log2(x) is an integer and > x/3 is an integer even exist? Is there a way I might go about proving > or disproving the existence of such a number?
There is no such number. 2 and 3 are what we call primes.
A prime p > 1 raised to some positive whole number power k, p^k, is not divisible by a prime q > 1 unless q = p. This is what lies behind the Fundamental Thm. of Arithmetic, that every positive integer is either a unit (1), a prime, or a unique product of primes (up to rearranging the factors' ordering).
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.
Therefore we proved by induction that 3 doesn't divide 2^k for any whole number k = 1,2,3,... . QED
It's also easy to show using arithmetic modulo 3, if that appeals to you.
regards, chip

