Take the 2-minute tour ×

tl;dr.: Is there any number for which $2^{i}\mod 3 = 0$ where $i \in \mathbb{N}$

Some friends and I made a bet recently. Basically, if you are 3 persons who are to share a pizza, and you start out by cutting it into 4 even sized pieces, can you ever keep doubling the number of slices so that everyone will be able to pick up the same amount of pieces and get the same amount of pizza?

We did some mathematics on this ourselves, but seeing as we're all IT-engineers, our math skills are quite rusty :) We did come up with a small application to check it out, and it seems that there is no solution for $i < 1000$ or so. However, we're not quite satisfied with this solution. Can anyone provide a proof that it will never happen (or the opposite)? :)

English is not my first language, so I might not have been able the formulate the question clear enough. If more information is needed, please ask :)

share|improve this question
No. You are asking for a number which is a power of 2 and is divisible by 3. This is impossible by unique factorization of integers into prime numbers (The fundamental theorem of arithmetic). –  KotelKanim Oct 14 '11 at 8:09
And they say number theory has no real world application. –  Joel Cohen Oct 14 '11 at 14:58
So did you win the bet or lose it? ;) –  Srivatsan Oct 14 '11 at 18:43
Sadly, I lost it :( –  cwap Oct 15 '11 at 18:39
Also, in the future, please try to use titles for your posts that help people browsing the titles to decide whether they might be able to help in your question. Eg. here you could use the title “Is there a power of two divisible by three?” or “Splitting pizza to three people evenly by repeatedly halving slices”. –  Zsbán Ambrus Mar 4 '12 at 12:17
add comment

3 Answers

up vote 10 down vote accepted

No, you can't, because the decomposition of a number into primes is unique and a $3$ does not appear in the prime decomposition of $2^i$.

share|improve this answer
add comment

On the other hand, if you're willing to cut infinitely often, you cut the pizza into four equal pieces, then take one piece each, and repeat with the remaining piece. If you do this exponentially faster you can finish the pizza in a finite amount of time.

share|improve this answer
One might hungry around step 5, however! –  JavaMan Oct 14 '11 at 18:03
On the other other hand, if you're willing to allow an infinite amount of toppings on your pizza... (^^ ?!?!) –  The Chaz 2.0 Oct 14 '11 at 18:09
add comment

For an argument without appealing to prime factorization, just note the following fact: the product of two odd numbers is odd.

Now suppose that we could write $2^i = 3n$ for some integer $n$. $2^i$ is clearly even, so $n$ must be even: $n = 2m$ for some integer $m$. Therefore, dividing both sides by 2, we have $2^{i-1} = 3m$, so $2^{i-1}$ can also be written as a multiple of 3. Repeating this process $i$ times, we find that $2$ can be written as a multiple of $3$, which is absurd.

share|improve this answer
add comment

Your Answer


