To determine if a number is divisible by 3 in binary, you can use a test similar to the divisibility rule for 11 in the decimal system: find the alternating sum of the bits.
If the result is divisible by 3, the original binary number is also divisible by 3.
The binary divisibility rule for 3 explained
The core of this rule lies in how the powers of 2 behave when divided by 3, which is best understood using modular arithmetic.
-
Examine the powers of 2 modulo 3. Counting from the rightmost bit, which is position 0, the value of each bit alternates between a remainder of 1 and a remainder of -1 (or 2) when divided by 3.
-
20=1≡1(mod3)2 to the 0 power equals 1 triple bar 1 space open paren mod 3 close paren
20=1≡1(mod3)
-
21=2≡-1(mod3)2 to the first power equals 2 triple bar negative 1 space open paren mod 3 close paren
21=2≡−1(mod3)
-
22=4≡1(mod3)2 squared equals 4 triple bar 1 space open paren mod 3 close paren
22=4≡1(mod3)
-
23=8≡-1(mod3)2 cubed equals 8 triple bar negative 1 space open paren mod 3 close paren
23=8≡−1(mod3)
-
And so on. The pattern is 1,-1,1,-1,...1 comma negative 1 comma 1 comma negative 1 comma point point point
1,−1,1,−1,...
.
-
-
Represent the binary number as a sum of powers of 2. Any binary number can be written as a sum of powers of 2, where each power is multiplied by either 0 or 1 (the bit at that position). For example, the binary number 110121101 sub 2
11012
is equal to (1⋅23)+(1⋅22)+(0⋅21)+(1⋅20)open paren 1 center dot 2 cubed close paren plus open paren 1 center dot 2 squared close paren plus open paren 0 center dot 2 to the first power close paren plus open paren 1 center dot 2 to the 0 power close paren
(1⋅23)+(1⋅22)+(0⋅21)+(1⋅20)
.
-
Apply modular arithmetic. To find the remainder of the binary number when divided by 3, replace each power of 2 with its corresponding remainder modulo 3.
-
11012≡(1⋅(-1))+(1⋅1)+(0⋅(-1))+(1⋅1)(mod3)1101 sub 2 triple bar open paren 1 center dot open paren negative 1 close paren close paren plus open paren 1 center dot 1 close paren plus open paren 0 center dot open paren negative 1 close paren close paren plus open paren 1 center dot 1 close paren space open paren mod 3 close paren
11012≡(1⋅(−1))+(1⋅1)+(0⋅(−1))+(1⋅1)(mod3)
-
≡-1+1+0+1(mod3)triple bar negative 1 plus 1 plus 0 plus 1 space open paren mod 3 close paren
≡−1+1+0+1(mod3)
-
≡1(mod3)triple bar 1 space open paren mod 3 close paren
≡1(mod3)
-
Since the remainder is 1, 110121101 sub 2
11012
(which is 131013 sub 10
1310
) is not divisible by 3.
-
-
Simplify the calculation. The pattern of $1sands a n d
𝑠𝑎𝑛𝑑
-1$s shows that you can simply sum the bits in the even-numbered positions and subtract the sum of the bits in the odd-numbered positions.
- Even positions (0, 2, 4, ...): These correspond to powers of 2 with a remainder of 1 modulo 3.
- Odd positions (1, 3, 5, ...): These correspond to powers of 2 with a remainder of -1 (or 2) modulo 3.
- If the total number of '1's in even positions equals the total number of '1's in odd positions, their difference is 0, which is divisible by 3.
Practical application of the rule
There are two primary methods to apply this rule in practice:
Method 1: The alternating sum of bits
-
Step 1: Starting from the rightmost bit (position 0), sum the bits in all the even positions (20,22,24,...2 to the 0 power comma 2 squared comma 2 to the fourth power comma point point point
20,22,24,...
).
-
Step 2: Sum the bits in all the odd positions (21,23,25,...2 to the first power comma 2 cubed comma 2 to the fifth power comma point point point
21,23,25,...
).
-
Step 3: Subtract the sum of the odd-position bits from the sum of the even-position bits.
-
Step 4: If the result is divisible by 3, the original number is divisible by 3.
**Example 1: Is 100121001 sub 2
10012
divisible by 3?**
-
**Decimal equivalent:**10012=9101001 sub 2 equals 9 sub 10
10012=910
. Yes, it's divisible by 3.
-
Applying the rule:
-
Binary number: 100121001 sub 2
10012
-
Positions (from right): 3, 2, 1, 0
-
Odd positions (1, 3): a1=0a sub 1 equals 0
𝑎1=0
, a3=1a sub 3 equals 1
𝑎3=1
. Sum = 0+1=10 plus 1 equals 1
0+1=1
.
-
Even positions (0, 2): a0=1a sub 0 equals 1
𝑎0=1
, a2=0a sub 2 equals 0
𝑎2=0
. Sum = 1+0=11 plus 0 equals 1
1+0=1
.
-
Difference: 1−1=01 minus 1 equals 0
1−1=0
. Since 0 is divisible by 3, 100121001 sub 2
10012
is divisible by 3.
-
**Example 2: Is 110121101 sub 2
11012
divisible by 3?**
-
**Decimal equivalent:**11012=13101101 sub 2 equals 13 sub 10
11012=1310
.
-
Applying the rule: Sum of bits in odd positions (1, 3) is 1. Sum of bits in even positions (0, 2) is 2. The difference is 2−1=12 minus 1 equals 1
2−1=1
, which is not divisible by 3. Therefore, 110121101 sub 2
11012
is not divisible by 3.
Method 2: Grouping bitsThis method uses the property that 22≡1(mod3)2 squared triple bar 1 space open paren mod 3 close paren
22≡1(mod3)
. Group the binary number into pairs of bits from the right. Convert each pair to its decimal value and sum these values. If the sum is divisible by 3, the original number is also divisible by 3.
**Example: Is 101101021011010 sub 2
10110102
divisible by 3?**
-
**Decimal equivalent:**10110102=90101011010 sub 2 equals 90 sub 10
10110102=9010
.
-
Applying the rule: Grouping gives 1|01|10|1021 the absolute value of 01 end-absolute-value 10 vertical line 10 sub 2
1|01|10|102
. The decimal values of these groups are 1, 1, 2, and 2. Their sum is 1+1+2+2=61 plus 1 plus 2 plus 2 equals 6
1+1+2+2=6
. Since 6 is divisible by 3, 101101021011010 sub 2
10110102
is divisible by 3.
Why this works: A proof using modular arithmetic
A binary number N=anan−1...a1a0cap N equals a sub n a sub n minus 1 end-sub point point point a sub 1 a sub 0
𝑁=𝑎𝑛𝑎𝑛−1...𝑎1𝑎0
can be written as N=∑k=0nak⋅2kcap N equals sum from k equals 0 to n of a sub k center dot 2 to the k-th power
𝑁=𝑛𝑘=0𝑎𝑘⋅2𝑘
. Since 2k≡(-1)k(mod3)2 to the k-th power triple bar open paren negative 1 close paren to the k-th power space open paren mod 3 close paren
2𝑘≡(−1)𝑘(mod3)
, we can substitute this into the expression for Ncap N
𝑁
:N≡∑k=0nak⋅(-1)k(mod3)cap N triple bar sum from k equals 0 to n of a sub k center dot open paren negative 1 close paren to the k-th power space open paren mod 3 close paren
𝑁≡𝑛𝑘=0𝑎𝑘⋅(−1)𝑘(mod3)
.This sum is equivalent to the difference between the sum of bits at even positions and the sum of bits at odd positions: N≡(a0+a2+a4+...)−(a1+a3+a5+...)(mod3)cap N triple bar open paren a sub 0 plus a sub 2 plus a sub 4 plus point point point close paren minus open paren a sub 1 plus a sub 3 plus a sub 5 plus point point point close paren space open paren mod 3 close paren
𝑁≡(𝑎0+𝑎2+𝑎4+...)−(𝑎1+𝑎3+𝑎5+...)(mod3)
.
The grouping method works because 22=4≡1(mod3)2 squared equals 4 triple bar 1 space open paren mod 3 close paren
22=4≡1(mod3)
. By grouping bits in pairs (a2k+1a2k)2open paren a sub 2 k plus 1 end-sub a sub 2 k end-sub close paren sub 2
(𝑎2𝑘+1𝑎2𝑘)2
, their decimal value is a2k+1⋅2+a2ka sub 2 k plus 1 end-sub center dot 2 plus a sub 2 k end-sub
𝑎2𝑘+1⋅2+𝑎2𝑘
. When considering the entire number modulo 3, due to 4k≡1(mod3)4 to the k-th power triple bar 1 space open paren mod 3 close paren
4𝑘≡1(mod3)
, the value of the number modulo 3 is equivalent to the sum of the decimal values of these bit pairs modulo 3.