# 3.3: Divisibility rules revisited

$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$$$\newcommand{\AA}{\unicode[.8,0]{x212B}}$$

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:

This page titled 3.3: Divisibility rules revisited is shared under a CC BY-NC-SA license and was authored, remixed, and/or curated by Pamini Thangarajah.