binary: how to recognize a multiple of 7?

Question

having a binary number, how can I systematically see if it is a multiple of 7? (no conversion possible, binary only)

Answer 1

7 = 111
14 = 1110
21 = 10101
28 = 11100
35 = 100011
42 = 101010
49 = 110001
56 = 111000

Break them into groups of 3. Add the groups. Repeat if the answer is more than 3 digits. If the final result is 111, then it is a multiple of 7.

Actually, this is an extension of octal (base-8) which explain why this works. Similar to the rule of 9 in base 10, there is a rule of 7 in base 8. Since 3 binary digits equate to a single octal digit, you have the same thing.

In octal:
7 = 7 base 8
14 = 16 base 8
21 = 25 base 8
28 = 34 base 8
etc.

Answer 2

I'll illustrate by determining whether the binary number 11010001111110010 is a multiple of 7. First, break the number into blocks of three bits, starting from the right:

11 010 001 111 110 010

Add up each block in binary:

....010
....110
....111
....001
....010
....+11
....------
10101

Apply this trick recursively until you are left with a single block of three bits:

10 101

101
+10
------
111

If you obtain the sequence 111 (as we have here), then the number is divisible by 7, otherwise it is not.

Why this works: If we let b_1, b_2... b_n be the blocks of three bits from right to left (so the representation of the binary number is b_nb_(n-1)b(n-2)... b_3b_2b_1), the value of the number is then:

[k=1, n]∑(b_k*8^(k-1))

But since 8≡1 mod 7, we have that this sum is congruent to

[k=1, n]∑b_k

mod 7. In other words, any binary number is congruent, mod 7, to the sum of the blocks of three digits. So to determine whether a given binary number is divisible by seven, it suffices to find the sum of its digit block and see whether that is divisible by seven (which is 111 in binary). We can apply this trick recursively, until we are left with only a single digit block, which is trivial to check.

Answer 3

Add every three digits.

So if your binary number is:

1001011110

Write it as:

1,101,011,110

Now add up these values:

110
011
101
001
===
1111

Keep doing this until you get to a 3 digit binary number. In this case the next step is:

111
001
-----
1000

Then:
000
001
-----
001


Then the original number is divisible by 7 if and only if the resulting number is '111.'

Another way to do it is to subtract 3 times the last digit from the rest of the digits until you get to a small number.

10101

Last digit is 1
Rest of the digits are 1010.
Subtract '11' from '1010' to get '111.'

The new number is divisible by 7 only when the previous number was divisible by 7. Repeat until you get to a number between 0 and 6.

(111 => 11 - 11 = 0.)

Answer 4

There's no way, just like in base 10.