Associated Topics || Dr. Math Home || Search Dr. Math

### 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

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
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/
```
Associated Topics:
High School Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search