|
|
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
|
|
