Question

Develop a test for divisibility of a positive integer nby 3based on the binary expansion of n.

Short answer

n is divisible by 3 when$(-1{)}^{k}ak+(-1{)}^{k-1}{a}_{k-1}+\dots -a_3+a_2-a_1+a_0$ is a multiple of .

Step-by-step solution

Step 1

DEFINITIONS

If the $\ textbf {base b base representation of n } $ is $a_k\dots a_2{a}_1{a}_0$, then

$n=a_k{b}^k+a_{k-1}{b}^{k-1}+\dots .+a_{1}b+a_0$

a divides b if there exists an integer such that

Notation: a|b

Division algorithm Let n be an integer and d a positive integer. Then there are unique integers q and r with 0 < r < d such that n = dq + r

q is called the quotient and r is called the remainder

q = n div

r = n mod

a is congruent to b modulo m if m divides a - b . Notation: a = b (mod m)

Step 2

SOLUTION

We want to determine how can we use the binary expansion of an integer to determine whether n is divisible by 3

When n is divisible by 3 , then its binary expansion (base 2 representation) needs to be divisible by :

$8\text{divides}{a}_k{2}^k+a_{k-1}{2}^{k-1}+\dots ..+a_{1}2+a_0$

By the definition of divides and the division algorithm:

$\left(a_k{2}^k+a_{k-1}{2}^{k-1}+\dots +a_{1}2+a_0\right)mod3=3mod3=0$

Since 2 = 1 (mod 3) :

$\left(a_k(-1{)}^k+a_{k-1}(-1{)}^{k-1}+\dots +a_1(-1)+a_0\right)mod3=0$

However, (- 1) = 1 when k even and (- 1) = - 1 when odd:

$\left((-1{)}^k{a}_k+(-1{)}^{k-1}{a}_{k-1}+\dots .-a_3+a_2-a_1+a_0\right)mod3=0$

Thus then implies that n is divisible by 3 when

$(-1{)}^{k}ak+(-1{)}^{k-1}{a}_{k-1}+\dots -a_3+a_2-a_1+a_0\text{is a multiple of}3.$