3.3: Divisibility rules revisited

Thinking out Loud

Can any integer $n$ be written as a sum of distinct powers of $2$?

Example $\PageIndex{1}$:

Express $2019$ as a sum of distinct powers of $2$?

Note that, $10 \equiv 1 ( mod \,\,3), 10 \equiv 1 ( mod\, 9),$ and $10 \equiv (-1)( mod \,\,11),$.

Let $x \in \mathbb{Z_+}$.

Then $$x= d_n10^n +d_{n-1}10^{n-1}+ \cdots+ d_2 10^2+d_110^1+d_0,$$

which implies

$$x= 10( d_n10^{n-1} +d_{n-1}10^{n-2}+ \cdots+ d_2 10+d_1)+d_0.$$

Thus we can express $x$ as $10 a+b$, where $b=d_0$ is the ones digit of $x$, and $a= d_n10^{n-1} +d_{n-1}10^{n-2}+ \cdots+ d_2 10+d_1$.

Divisibility by $2=2^1:$

Let $x= d_n10^n +d_{n-1}10^{n-1}+ \cdots+ d_2 10^2+d_110^1+d_0\in \mathbb{Z_+}$, then $2 \mid x$ iff $2 \mid d_0$. In other words, $2$ divides an integer iff the ones digit of the integer is either $0, 2, 4, 6,$ or $8$. That is. $x \equiv 0 (mod \,2)$ iff $d_0 \equiv 0 (mod \,2)$.

Proof:

Since $10 \equiv 0 (mod \,2)$ and $x=10 a+b$, $x \equiv 0 (mod \,2)$ iff $d_0 \equiv 0 (mod \,2)$.$\Box$

Divisibility by $5:$

Let $x= d_n10^n +d_{n-1}10^{n-1}+ \cdots+ d_2 10^2+d_110^1+d_0\in \mathbb{Z_+}$, then $5 \mid x$ iff $5 \mid d_0$. In other words, $5$ divides an integer iff the ones digit of the integer is either $0,$ or $5$.

That is. $x \equiv 0 (mod \,\,5)$ iff $d_0 \equiv 0 (mod \,\,5)$.

Proof:

Since $10 \equiv 0 (mod \,5)$ and $x=10 a+b$, $x \equiv 0 (mod \,5)$ iff $d_0 \equiv 0 (mod \,5)$.$\Box$

Divisibility by $10:$

Let $x= d_n10^n +d_{n-1}10^{n-1}+ \cdots+ d_2 10^2+d_110^1+d_0\in \mathbb{Z_+}$, then $10 \mid x$ iff $10 \mid d_0$. In other words, $10$ divides an integer iff the ones digit of the integer is $0,$.

That is. $x \equiv 0 (mod \,10)$ iff $d_0 \equiv 0 (mod \,10)$.

Proof:

Since $10 \equiv 0 (mod \,10)$ and $x=10 a+b$, $x \equiv 0 (mod \,10)$ iff $d_0 \equiv 0 (mod \,10)$.$\Box$

Divisibility by $4=2^2:$

Let $x= d_n10^n +d_{n-1}10^{n-1}+ \cdots+ d_2 10^2+d_110^1+d_0\in \mathbb{Z_+}$, then $4 \mid x$ iff $4 \mid d_1d_0$. That is. $x \equiv 0 (mod \,4)$ iff $d_1d_0 \equiv 0 (mod \,4)$.

Proof:

Let $x$ be an integer. Then

$x= d_n10^n +d_{n-1}10^{n-1}+ \cdots+ d_2 10^2+d_110^1+d_0$, which implies

$x= 100( d_n10^{n-2} +d_{n-1}10^{n-3}+ \cdots+ d_2)+ 10d_1+d_0=100( d_n10^{n-2} +d_{n-1}10^{n-3}+ \cdots+ d_2)+ d_1d_0$.

Since $100 \equiv 0 (mod \,4)$, $x=100 a+ d_1d_0$, $x \equiv 0 (mod \,4)$ iff $d_1d_0 \equiv 0 (mod \,4)$.$\Box$

Divisibility by $8=2^3:$

Let $x= d_n10^n +d_{n-1}10^{n-1}+ \cdots+ d_2 10^2+d_110^1+d_0\in \mathbb{Z_+}$, then $8 \mid x$ iff $8 \mid d_2d_1d_0$. That is. $x \equiv 0 (mod \,8)$ iff $d_2d_1d_0 \equiv 0 (mod \,8)$.

Proof:

Let $x$ be an integer. Then

$x= d_n10^n +d_{n-1}10^{n-1}+ \cdots+ d_2 10^2+d_110^1+d_0$, which implies

$x= 10^3( d_n10^{n-3} +d_{n-1}10^{n-4}+ \cdots+ d_3)+ 100d_2+10d_1+d_0=10^3( d_n10^{n-3} +d_{n-1}10^{n-4}+ \cdots+ d_3)+ d_2d_1d_0$.

Since $1000 \equiv 0 (mod \,8)$, $x=1000 a+ d_2d_1d_0$, $x \equiv 0 (mod \,8)$ iff $d_2d_1d_0 \equiv 0 (mod \,8)$.$\Box$

A similar argument can be made for divisibility by $2^n$, for any positive integer $n$. The following results follows from the fact that,

$x= d_n10^n +d_{n-1}10^{n-1}+ \cdots+ d_2 10^2+d_110^1+d_0 = d_n(10^n-1) +d_{n-1}(10^{n-1}-1)+ \cdots+ d_2 (10^2-1)+d_1(10^1-1)+ (d_n+d_{n-1}+ \cdots+ d_1+ d_0)$.

Divisibility by $3:$

Let $x= d_n10^n +d_{n-1}10^{n-1}+ \cdots+ d_2 10^2+d_110^1+d_0\in \mathbb{Z_+}$, then $3 \mid x$ iff $3$ divides sum of its digits.

Proof:

Let $x$ be an integer. Then

$x= d_n10^n +d_{n-1}10^{n-1}+ \cdots+ d_2 10^2+d_110^1+d_0$, which implies $x= d_n(10^n-1) +d_{n-1}(10^{n-1}-1)+ \cdots+ d_2 (10^2-1)+d_1(10^1-1)+ (d_n+d_{n-1}+ \cdots+ d_1+ d_0)$.

Hence, $x (mod \,3) \equiv d_n(10^n-1) +d_{n-1}(10^{n-1}-1)+ \cdots+ d_2 (10^2-1)+d_1(10^1-1)) (mod \,3)+ (d_n+d_{n-1}+ \cdots+ d_1+ d_0) (mod \,3).$  Notice that $(10^n-1) \equiv 0 (mod \, 3),$ for all positive integer $n.$

Therefore, $x (mod \,3) \equiv (d_n+d_{n-1}+ \cdots+ d_1+ d_0) (mod \,3).$

 Thus, $3 \mid x$ iff $3$ divides sum of its digits.

 

Divisibility by $9=3^2:$

Let $x= d_n10^n +d_{n-1}10^{n-1}+ \cdots+ d_2 10^2+d_110^1+d_0\in \mathbb{Z_+}$, then $9 \mid x$ iff $9$ divides sum of its digits.

Proof:

Let $x$ be an integer. Then

$x= d_n10^n +d_{n-1}10^{n-1}+ \cdots+ d_2 10^2+d_110^1+d_0$, which implies $x= d_n(10^n-1) +d_{n-1}(10^{n-1}-1)+ \cdots+ d_2 (10^2-1)+d_1(10^1-1)+ (d_n+d_{n-1}+ \cdots+ d_1+ d_0)$.

Hence, $x (mod \,9) \equiv d_n(10^n-1) +d_{n-1}(10^{n-1}-1)+ \cdots+ d_2 (10^2-1)+d_1(10^1-1)) (mod \,9)+ (d_n+d_{n-1}+ \cdots+ d_1+ d_0) (mod \,9).$  Notice that $(10^n-1) \equiv 0 (mod \, 9),$ for all positive integer $n.$

Therefore, $x (mod \,9) \equiv (d_n+d_{n-1}+ \cdots+ d_1+ d_0) (mod \,9).$

 Thus, $9 \mid x$ iff $9$ divides sum of its digits.

Divisibility by $7:$

$7 \mid x$ iff $7$ divides the absolute difference between $a-2b$, where $x=10 a+b$, and, $b=d_0$ is the ones digit of $x$ and $a= d_n10^{n-1} +d_{n-1}10^{n-2}+ \cdots+ d_2 10+d_1$.

Proof:

Divisibility by $11:$

$11 \mid x$ iff $11$ divides the absolute difference between alternate sum.

Proof: