Power of 2 divisible by 3

[Xleonar...@gmail.com]

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?

[Ant...@gmail.com]

Guess what, I cannot seem to find a power of 3 divisible by 2, either.
Isn't that great?

[gwl...@nukove.com]

There can be no powers of two divisible by three. Powers of two have
only two as a prime factor, and by unique factorization with integers,
three cannot be a divisor. Stop wasting your time...

[mensa...@aol.com]

As mentioned by others, there is no such number.

However, powers of 2 alternate between being congruent to
1 (mod 3) and 2 (mod 3) depending on whether the power is even
or odd.

So what you can say is:

If n is even, all 2**n - 1 are divisible by 3.
If n is odd, all 2**n + 1 are divisible by 3.

[Chip Eastham]

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

[Bart Goddard]

Xleonar...@gmail.com wrote:

> I cannot seem to find a power of 2 divisible by 3.

2^(3.17) is really close to 9.

Bart

[Carlos Moreno]

Chip Eastham wrote:

> [...]

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

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.

Carlos
--

[Gerry Myerson]

In article <Xns975B925FB...@129.250.170.91>,
Bart Goddard <godd...@netscape.net> wrote:

2^(19/12) is about 2.997, which is why 12 (musical) fifths
come very close to 7 octaves.

--
Gerry Myerson (ge...@maths.mq.edi.ai) (i -> u for email)

[Bill Dubuque]

Carlos Moreno <moreno_at_mo...@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

[Ant...@gmail.com]

Correct. First 2 ^ 0 = 1, 1 - 1 = 0 and 2 ^ 1 = 2, 2 + 1 = 3. Second
for any x = 3 * k + 1, 2 * x = 3 * ( 2 * k) + 2 and for any x = 3 * k +
2, 2 * x = 3 * ( 2 * k + 1) + 1, which means for any x = 1( mod 3), 2 *
x = 2( mod 3) and for any x = 2( mod 3), 2 * x = 1( mod 3). Here we
come to the conclusion "If n is even, all 2**n - 1 are divisible by 3.

[The Ghost In The Machine]

In sci.math, Xleonar...@gmail.com
<Xleonar...@gmail.com>
wrote
on 30 Jan 2006 10:54:45 -0800
<1138647285.1...@g14g2000cwa.googlegroups.com>:

Theorem. No nonnegative integral power of 2 is divisible by 3.

Proof. 2^0/3 = 1/3 = 0 + 1/3 clearly is not an integer,
and furthermore is expressable as j + k/3; see below.

For n >= 0, let 2^n/3 = j + k/3, where j and k are some integers,
k can be either +1 or -1. Then 2^(n+1)/3 = 2*j + 2*k/3.

Case 1: k = +1. Then 2^(n+1)/3 = (2*j+1) - 1/3.
Case 2: k = -1. Then 2^(n+1)/3 = (2*j-1) + 1/3.

Therefore, by induction, 2^n/3 = j + k/3, where k = +1 or -1,
and the theorem is proved.

* * *

Theorem. 4^n = 1 (mod 3) for all n > 0.

Proof. 4 = 1 (mod 3) therefore 4^n = 1^n = 1 (mod 3). QED

Corollary. No nonnegative integral power of 2 is divisible by 3.

Proof. For even powers of two this is obvious. For odd powers
of two 2^(2j+1) = 2^(2j) * 2 = 4^j * 2 = 1 * 2 = 2 (mod 3). QED

* * *

Theorem: The expansion 1/3 is infinite in base 2.

Proof: The standard long division algorithm yields the following.

shift = 1, digit 0 = 0, remainder 1
shift = 2, digit 1 = 0, remainder 2
shift = 4, digit 2 = 1, remainder 1
shift = 2, digit 3 = 0, remainder 2
shift = 4, digit 2 = 1, remainder 1
shift = 2, digit 3 = 0, remainder 2

Clearly this is repeating and will never hit zero. (This can be
rigorously proven by noting that the number of possible remainders
is finite; furthermore, in this particular case the remainders
never hit zero. The proof is esssentially similar to the first.)

Corollary #1: 1/3 is not a multiple of 2^n for some (negative) integer n.

Corollary #2: There is no nonnegative integral power of 2 divisible by 3.

* * *

At this point they're really variations on a theme.
I could walk through the formal definition of a Turing
machine with a 2-digit alphabet that divides an input
number on its tape by 3 (11 in base 2), then feed it the
input 1.000...., for example, but that would be nearly
identical to my third proof, above. There might be some
very esoteric proofs using limits or something (at least
one classic proof of transcendentiality of a number is
based on such), but I'd have to look.

--
#191, ewi...@earthlink.net
It's still legal to go .sigless.

[Shmuel (Seymour J.) Metz]

In <1138647285.1...@g14g2000cwa.googlegroups.com>, on
01/30/2006

at 10:54 AM, Xleonar...@gmail.com said:

>I cannot seem to find a power of 2 divisible by 3.

That's because you're working in Z, the ring of integers. Try it in,
e.g., Z/5, where 2^3 is 3 (8=3+5).

--
Shmuel (Seymour J.) Metz, SysProg and JOAT <http://patriot.net/~shmuel>

Unsolicited bulk E-mail subject to legal action. I reserve the
right to publicly post or ridicule any abusive E-mail. Reply to
domain Patriot dot net user shmuel+news to contact me. Do not
reply to spam...@library.lspace.org

[Chip Eastham]

Shmuel (Seymour J.) Metz wrote:
> In <1138647285.1...@g14g2000cwa.googlegroups.com>, on
> 01/30/2006
> at 10:54 AM, Xleonar...@gmail.com said:
>
> >I cannot seem to find a power of 2 divisible by 3.
>
> That's because you're working in Z, the ring of integers. Try it in,
> e.g., Z/5, where 2^3 is 3 (8=3+5).

In Z/5Z, already 2 is divisible by 3. No need to raise to a power...

-- chip

[Gerry Myerson]

In article <1138749336.7...@o13g2000cwo.googlegroups.com>,
"Chip Eastham" <hard...@gmail.com> wrote:

OK, so is there any reasonable mathematical system where there is
an entity recognizable as a 2 that is not divisible by an entity
recognizable as a 3, but where some power of that 2 is divisible
by that 3?

[matt...@dodgeit.com]

Gerry Myerson

>OK, so is there any reasonable mathematical system where there is an
>entity recognizable as a 2 that is not divisible by an entity recognizable
>as a 3, but where some power of that 2 is divisible by that 3?

Well, in Z/10Z we have 2 and 3 distinct but 16 is congruent to 6 which
is 2*3... Moreover, 2 is a zero divisor in Z/10Z but 3*7 = 21 which is
congruent to 1 mod 10 so 3 is not a zero divisor and thus doesn't
divide 2.

[Chip Eastham]

The fact (3 is not a zero divisor) is correct, but the conclusion is
wrong. Not being a zero divisor in Z/10Z is tantamount to being
a unit, and any element is "divisible" by a unit (because dividing
by 3 is equivalent to multiplying by its reciprocal 7:

2 = 4*3 mod 10

To take a stab at Gerry's question, suppose f:Z-->R is a ring
homomorphism, not necessarily onto, such that f(2^k) is divisible
by f(3) in R. Since f(3) = f(2) + f(1), it is pretty inescapable that
f(3) must also divide f(1) by the following argument:

f(3) divides f(2^k)^2 = f(4)^k, and f(3) divides f(4^k - 1) =
f(4^k)-f(1)

So the only escape hole I can see that might prevent concluding
that f(3) is a unit in R, and that f(3) thus already divides f(2) as
we discovered above, would be a "cheat" that ring homomorphism
doesn't require mapping the unit 1 of Z to the unit of R.

I will leave it someone with a more freshly unreasonable
mind to discover if such a "cheat" is actually feasible.

-- c

[Robert Israel]

In article <1138765849.6...@o13g2000cwo.googlegroups.com>,
Chip Eastham <hard...@gmail.com> wrote:

>> Gerry Myerson
>> >OK, so is there any reasonable mathematical system where there is an
>> >entity recognizable as a 2 that is not divisible by an entity recognizable
>> >as a 3, but where some power of that 2 is divisible by that 3?

>To take a stab at Gerry's question, suppose f:Z-->R is a ring

>homomorphism, not necessarily onto, such that f(2^k) is divisible
>by f(3) in R. Since f(3) = f(2) + f(1), it is pretty inescapable that
>f(3) must also divide f(1) by the following argument:
>
>f(3) divides f(2^k)^2 = f(4)^k, and f(3) divides f(4^k - 1) =
>f(4^k)-f(1)
>
>So the only escape hole I can see that might prevent concluding
>that f(3) is a unit in R, and that f(3) thus already divides f(2) as
>we discovered above, would be a "cheat" that ring homomorphism
>doesn't require mapping the unit 1 of Z to the unit of R.

>I will leave it someone with a more freshly unreasonable
>mind to discover if such a "cheat" is actually feasible.

R need not have a unit element at all, but its subring f(Z)
does (namely f(1)).

For any x and y in Z such that gcd(x,y) = 1 we have a x + b y = 1
for some a and b in Z, and therefore a f(x) + b f(y) = f(1).
So if f(y) divides f(x), it also divides f(1), and therefore
divides f(z) for all z in Z.

Robert Israel isr...@math.ubc.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada

[Minus XVII]

yes, nice, but I'll just correct the typo:

2^k = 3(2^k) - 2^(k+1).

thus:
I was going to say that the "map, below," was 3-colorable, but
the formatting became clear upon clicking for replying. anyway,
that is also the "neccesity" part of the 4-color proof,
a.k.a. "the tetrahedron, q.e.d." on a sphere
(more or less; your further result is the same,
as coloring/labelling the surrounding space .-)

> Please explain how a map demanding 5 colors can demand 5 colors without
> having 5 countries bordering each other? Anything except the specious
> argument about a 4-color graph not requiring 4 mutually adjacent
> countries! Consider the simple map below
> ----------------------------------------
> | A |
> |----------------------------------------|
> | | | |
> | B | C | D |
> | |______| |
> |__________ |___________ |

> If the analogy were valid, you could add country E between B & D, just
> below C and get a 5-color map . And there are no 5 countries bordering
> each other.

> But the analogy is not valid. Adding E actually makes the map 3-C.

> ------------------------------------------
> | A |
> |----------------------------------------|
> | | | |
> | B | C | D |
> | |______| |
> |_______ |__E__|_________|

--Give Earth a Trickier Dick Cheeny -- out of office, after gigayears!
http://larouchepub.com/other/2003/3045dems_dive_soros.html
http://tarpley.net/bush8.htm
http://www.benfranklinbooks.com/
http://members.tripod.com/~american_almanac
http://www.wlym.com/pdf/iclc/howthenation.pdf
http://larouchepub.com/other/2003/3048iraq_58_const.html
http://www.rand.org/publications/randreview/issues/rr.12.00/
http://www.rwgrayprojects.com/synergetics/plates/figs/plate01.html

[Gerry Myerson]

In article <drqstv$p3u$1...@nntp.itservices.ubc.ca>,
isr...@math.ubc.ca (Robert Israel) wrote:

> In article <1138765849.6...@o13g2000cwo.googlegroups.com>,
> Chip Eastham <hard...@gmail.com> wrote:
>
> >> Gerry Myerson
> >> >OK, so is there any reasonable mathematical system where there is an
> >> >entity recognizable as a 2 that is not divisible by an entity recognizable
> >> >as a 3, but where some power of that 2 is divisible by that 3?
>
> >To take a stab at Gerry's question, suppose f:Z-->R is a ring
> >homomorphism, not necessarily onto, such that f(2^k) is divisible
> >by f(3) in R. Since f(3) = f(2) + f(1), it is pretty inescapable that
> >f(3) must also divide f(1) by the following argument:
> >
> >f(3) divides f(2^k)^2 = f(4)^k, and f(3) divides f(4^k - 1) =
> >f(4^k)-f(1)
> >
> >So the only escape hole I can see that might prevent concluding
> >that f(3) is a unit in R, and that f(3) thus already divides f(2) as
> >we discovered above, would be a "cheat" that ring homomorphism
> >doesn't require mapping the unit 1 of Z to the unit of R.
>
> >I will leave it someone with a more freshly unreasonable
> >mind to discover if such a "cheat" is actually feasible.
>
> R need not have a unit element at all, but its subring f(Z)
> does (namely f(1)).
>
> For any x and y in Z such that gcd(x,y) = 1 we have a x + b y = 1
> for some a and b in Z, and therefore a f(x) + b f(y) = f(1).

This should perhaps be f(a) f(x) + f(b) f(y) = f(1),
but even if this is so your nice argument goes through.

> So if f(y) divides f(x), it also divides f(1), and therefore
> divides f(z) for all z in Z.

--

[Bill Dubuque]

isr...@math.ubc.ca (Robert Israel) writes:
>Chip Eastham <hard...@gmail.com> wrote:
>>>Gerry Myerson
>>>> OK, so is there any reasonable mathematical system where there is an
>>>> entity recognizable as a 2 that is not divisible by an entity recognizable
>>>> as a 3, but where some power of that 2 is divisible by that 3?
>>
>> To take a stab at Gerry's question, suppose f:Z-->R is a ring
>> homomorphism, not necessarily onto, such that f(2^k) is divisible
>> by f(3) in R. Since f(3) = f(2) + f(1), it is pretty inescapable that
>> f(3) must also divide f(1) by the following argument:
>>
>> f(3) divides f(2^k)^2 = f(4)^k, and f(3) divides f(4^k - 1) =
>> f(4^k)-f(1)
>>
>> So the only escape hole I can see that might prevent concluding
>> that f(3) is a unit in R, and that f(3) thus already divides f(2) as
>> we discovered above, would be a "cheat" that ring homomorphism
>> doesn't require mapping the unit 1 of Z to the unit of R.
>
>> I will leave it someone with a more freshly unreasonable
>> mind to discover if such a "cheat" is actually feasible.
>
> R need not have a unit element at all, but its subring f(Z)
> does (namely f(1)).
>
> For any x and y in Z such that gcd(x,y) = 1 we have a x + b y = 1
> for some a and b in Z, and therefore a f(x) + b f(y) = f(1).
> So if f(y) divides f(x), it also divides f(1), and therefore
> divides f(z) for all z in Z.

See the discussion between Arturo and I on 2003/11/7 (7 posts):
http://google.com/groups?threadm=y8zislz23dt.fsf%40nestle.ai.mit.edu

--Bill Dubuque