# Need some help settling a bet

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

• 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

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