Binary Divisibility by 10

Date: 04/07/99 at 21:28:03
From: Anna
Subject: Binary divisibility by 10

I was wondering how you can tell whether a binary number of arbitrary 
size is divisible by 10, without looking at the whole number. The
maximum size of consideration is really important, and within 32 bits
would be really good, although around 30 words (1 word = 32 bits) is
also okay. So is looking at either the most significant or least
significant end of the number.

I figured out that the number has to be divisible by 2 and 5.
Divisibility by 2 of a binary number is easy, but what about by 5? Or
is there another way of looking at the problem?

Thanks a lot.

Date: 04/08/99 at 16:54:49
From: Doctor Peterson
Subject: Re: Binary divisibility by 10

Hi, Anna. This is a great question!

I'd never thought much about divisibility rules for base 2 except 
those that carry over from base 10 (such as divisibility by 3 = 11 
base 2, which is the same as the rule for 11 base 10). But I managed 
to find a rule for binary divisibility by 5 by using some of the same 
techniques. 

It's a little tricky, but quite workable. Then I realized that since 
you're really working not with individual bits but with whole bytes or 
words, there's a much easier way to do it. I'll first show you the 
strictly binary method, since it can be instructive, then I'll show 
you the better way, which in fact is just like the decimal rule for 
divisibility by 3.

I'll work with the number 617283950 = 100100110010110000000101101110.

First split the number into odd and even bits (I'm calling "even" the 
bits corresponding to even powers of 2):

   100100110010110000000101101110
    0 1 0 1 0 0 1 0 0 0 1 1 0 1 0 even
   1 0 0 1 0 1 1 0 0 0 0 0 1 1 1  odd

Now in each of these, add and subtract the digits alternately, as in 
the standard test for divisibility by 11 in decimal (starting with 
addition at the right):

   100100110010110000000101101110
   +0-1+0-1+0-0+1-0+0-0+1-1+0-1+0 = -2
  +1-0+0-1+0-1+1-0+0-0+0-0+1-1+1  =  1

Now double the sum of the odd digits and add it to the sum of the even 
digits:

   2*1 + -2 = 0

If the result is divisible by 5, as in this case, the number itself is 
divisible by 5.

Since this number is also divisible by 2 (the rightmost digit being 
0), it is divisible by 10.

This algorithm can be applied to numbers of any size; the highest 
either sum can be is half the number of bits you're working with. And 
since the pattern repeats every 4 bits, you can work with one byte (or 
word, or long word) at a time, making a simple loop.

Now you're asking, how did I ever figure this out?

Here's what I did: I looked at powers of 2 modulo 5:

   2^0 =  1 =  1 mod 5
   2^1 =  2 =  2 mod 5
   2^2 =  4 = -1 mod 5
   2^3 =  8 = -2 mod 5
   2^4 = 16 =  1 mod 5
   now it repeats ...

(Two numbers are equal, or more properly "congruent," modulo 5, if 
they give the same remainder when they are divided by 5; the sum or 
product of numbers that are congruent mod 5 will still be congruent.)

Now a binary number is the sum of selected powers of 2. If the bits 
are, say, abcdef, then the number is

   f*2^0 =  1f =  1f mod 5
   e*2^1 =  2e =  2e mod 5
   d*2^2 =  4d = -1d mod 5
   c*2^3 =  8c = -2c mod 5
   b*2^4 = 16b =  1b mod 5
   a*2^5 = 32a =  2a mod 5
   -----         ---------
   abcdef =      2(e-c+a) + (f-d+b) mod 5

This is the formula I gave you. Now for the method I'm really 
recommending.

Remember I pointed out that the pattern repeats every 4 bits? That's 
because 2^4 = 16 = 1 mod 5. Rather than work in binary, we can work in 
hexadecimal, just adding up the hex digits (4-bit nibbles) of the 
number. If this sum is divisible by 5, the number itself is. Even 
better, you can work with a whole byte at a time (base 256), since 
256 = 1 mod 5 as well. That's about as simple as it can get: add all 
the bytes of the number, and if the sum is divisible by 5, the number 
is divisible by 5. The only disadvantage to working at this larger 
scale is that the sums will be larger; but for your 120-byte numbers 
the sum will be no more than 120*256 = 30720. If you don't want to 
check this for divisibity by 5 by dividing, you can apply the binary 
algorithm to it.

Here's why this works, in simple terms:

    a*256^0 + b*256^1 + c*256^2 + ... + z*256^n =
    a*1 + b*(255 + 1) + c*(255 + 1)^2 + ... + z*(255+1)^n =
    (a + b + c + ... + z) + 255*(something)

so if a+b+c+...+z is divisible by 5, then so is abc...z (base 256).

In our example, 617283950 = 24CB016E; 24+CB+01+6E = 15E = 350 (base 
10), which is divisible by 5; since 6E is even, 24CB016E is divisible 
by 10.

- Doctor Peterson, The Math Forum
  http://mathforum.org/dr.math/