Binary divisibility by 3

**mpekatsoula** · Nov5-09, 11:44 AM

Well i found this sentence: "If the number of even bits minus the number of odd bits is a multiple of 3 (e.g. -3,0,3,6, etc) then the number is divisible by three." Can anyone tell me the proof of this?
Thanks

**Gerenuk** · Nov5-09, 01:11 PM

These rules can be found from modular arithmetic.
http://en.wikipedia.org/wiki/Modular_arithmetic

For binary number in particular we can write the following equation for a binary number where all equations are taking mod 3
$LaTeX Code: (a_n\\dotsb a_3a_2a_1a_0)_b=2^n a_n+\\dotsb+ 2^3 \\cdot a_3+2^2\\cdot a_2+2\\cdot a_1+a_0=(-1)^n a_n+\\dotsb+ (-1) \\cdot a_3+(+1)\\cdot a_2+(-1)\\cdot a_1+a_0 $
Here you say that one has the alternatively add the bits and the final result will have the same divisibility by 3 as the complete binary number.

Have a look at Wikipedia and then ask, if something is unclear. I admit Wikipedia doesn't explain this well. Maybe you can also find a better reference.

**Gerenuk** · Nov5-09, 01:22 PM

Hmm, couldn't find a very concise summary of modular arithmetic. Basically what you need to know is that one can write equations where one only cares if the remainder to some division is the same. For example
$LaTeX Code: 9=19=29=\\dotsb\\qquad\\text{mod 10} $
since all numbers have the same remainder w.r.t. division by 10. Note that also
$LaTeX Code: 9=-1=-11=\\dotsb\\qquad\\text{mod 10} $
since in general you can add or subtract any multiple of 10 (in this case).

Now some rule are, that for you can replace any integer by another which gives the same remainder. For example
$LaTeX Code: 156=12\\cdot 13=2\\cdot 3=6\\qquad\\text{mod 10} $
as you can check for yourself.

You can do this in equations also at any instant of the calculation
$LaTeX Code: 1116=12\\cdot (89+4)=2\\cdot (9+4)=2\\cdot 13=2\\cdot 3=6\\qquad\\text{mod 10} $
where in some steps I replaced number by their remainder w.r.t. division by 10 (which is basically the last digit of the number)

That what I did for your problem
$LaTeX Code: 2^n=(-1)^n\\qquad\\text{mod 3} $
where I replaced 2 with the "equivalent" remainder-wise -1.

**mpekatsoula** · Nov5-09, 02:11 PM

Well thanks for the help! First time in my life i hear about modular arithmetic! It took me some time to understand but thanks to your answer i think i got it!