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

  • 15
    $\begingroup$ 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). $\endgroup$ – KotelKanim Oct 14 '11 at 8:09
  • 7
    $\begingroup$ And they say number theory has no real world application. $\endgroup$ – Joel Cohen Oct 14 '11 at 14:58
  • 2
    $\begingroup$ So did you win the bet or lose it? ;) $\endgroup$ – Srivatsan Oct 14 '11 at 18:43
  • $\begingroup$ Sadly, I lost it :( $\endgroup$ – cwap Oct 15 '11 at 18:39
  • $\begingroup$ 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”. $\endgroup$ – Zsbán Ambrus Mar 4 '12 at 12:17

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


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.

  • 1
    $\begingroup$ One might hungry around step 5, however! $\endgroup$ – JavaMan Oct 14 '11 at 18:03
  • 2
    $\begingroup$ On the other other hand, if you're willing to allow an infinite amount of toppings on your pizza... (^^ ?!?!) $\endgroup$ – The Chaz 2.0 Oct 14 '11 at 18:09

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.