# Re: divisibility conditions for binary numbers

*From*: "Mitch" <maharri@xxxxxxxxx>*Date*: 7 Apr 2006 10:28:48 -0700

Robert Israel wrote:

Larry Hammick <larryhammick@xxxxxxxxx> wrote:

the OP wrote

Could anyone has some idea on divisibility of binary numbers by 3,5,6,7

I don't think much can be said, but given a binary number

x = \sum_n ( k_n 2^n )

where each digit k_n is 0 or 1, let

A = the number of k_n's which are 1 and n is even

B = the number of k_n's which are 1 and n is odd

Then x is divisible by 3 if and only if A-B is divisible by 3.

E.g 1110101 (binary) is divisible by 3 since A=4 and B=1.

For 5, note that 2^j == 1, 2, -1, -2 mod 5 for j == 0, 1, 2, 3 mod 4

respectively. So let A, B, C, D be the number of k_n which are 1

with n congruent to 0, 1, 2, 3 mod 4, and take A + 2 B - C - 2 D.

Then x is divisible by 5 iff the result is divisible by 5.

E.g. for 11110101 we have A = 2, B = 1, C = 2, D = 1, result = 0

so it's divisible by 5. You may find it easier to start at the right

end and go digit-by-digit, adding or subtracting 1 or 2 for each

1 as appropriate.

You can construct a similar trick for divisibility by any odd

integer.

Yes, this is a cute trick that turns up as an exercise in automata

theory. It generalizes easily for -any- divisor/modulus and any base.

Such things are always finite automata/regular languages, where the

states are the moduli, and the transitions are the digits. Reading a

numeral from MSD to least, each new digit multiplies by the base and

adds the digit, and the state you're left in is the modulus of the

numeral. For example,

Binary numbers divisible by 3 have the DFA (follow the edges as you

read the digits left to right, starting from the leftmost state):

1 0

----------> ----------->

mod3=0 mod3=1 mod3=2

<---------- <----------

1 0

(with a self loop labeled 0 on the first state, and a self loop labeled

1 on the last)

Creating the DFA is not too hard: for a given state (modulus) a new

digit corresponds to multiplying by the base and adding the digit,

leading to a new state. E.g., if your binary number (so far) is 2 mod 3

(that is = 3k+2), then appending a 1 doubles the number and adds 1 or

2*(3k+2)+1 = 6k+5 = 6k'+2 = 3k''+2 which is in the same modulus class.

Do the same thing for all moduli and all digits.

The corresponding regular expression (for mod3=0) is:

(0 + 1(01*0)*1)*

Notice that 1001_2 = 9 is divisible by 3, and by the regular

expression, we could put any number of 1's beteen the pair of 0's and

still be divisible by 3: 10101_2 = 21, 101101_2 = 45, 1011101_2 = 93,

etc...

Mitch

.

**References**:**divisibility conditions for binary numbers***From:*Shishir

**Re: divisibility conditions for binary numbers***From:*Larry Hammick

**Re: divisibility conditions for binary numbers***From:*Robert Israel

- Prev by Date:
**gcd and determinant** - Next by Date:
**subsets and homemorhism** - Previous by thread:
**Re: divisibility conditions for binary numbers** - Next by thread:
**Re: divisibility conditions for binary numbers** - Index(es):