Question

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

Short answer

n is divisible by 8 when$a_0=a_1=a_2=0$ .

Step-by-step solution

Step 1

DEFINITIONS

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

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

a divides b if there exists an integer such that

Notation:

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

q is called the quotient and r is called the remainder

q = ndiv d

r = n mod d

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

Step 2

SOLUTION

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

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

$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)mod8=8mod8=0$

Since $2^3\equiv 8,a_i{2}^{i}mod8=0\text{for}i=3,4,\dots ,k$.

$\left(a_2{2}^2+a_{1}2+a_0\right)mod8=0$

Since $a_2{2}^2+a_{1}2+a_0$is an integer from 0 to 7 , we note that $a_2{2}^2+a_{1}2+a_0$is only divisible by 8 when $a_2{2}^2+a_{1}2+a_0=0$and thus we require $a_0=a_1=a_2=0$.