Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

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


Math Forum » Discussions » sci.math.* » sci.math.independent

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Chip Eastham

Posts: 2,341
Registered: 12/13/04
Re: Power of 2 divisible by 3
Posted: Jan 30, 2006 2:36 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply


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




Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.